leetcode 題解
92. 反轉鏈表 II
方法一：
提交程式碼：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
// 由於leetcode提交默認的是沒有頭結點的，故需要內部創建一個頭結點方便使用 struct ListNode* reverseBetween(struct ListNode* head, int m, int n) { if(n < m) return; if(n == m) return head; struct ListNode h = {0, head}; //設置一個頭節點【普通結構體變數】,處理m=1的情況 struct ListNode* pre = &h; //指針變數賦值 struct ListNode *p = pre ->next,*q,*t; int i = 1; while(i < m) { pre = p; p = p->next; ++i; } t = p; //t 記錄翻轉部分的起點 if(m < n) { p = p->next; ++i; } while(i <= n) { q = p; p = p->next; ++i; q->next = pre->next; pre->next = q; // 每次將第一步找到的結點指向反轉後的頭結點 } t->next = p; //將反轉的起點next指向反轉後面的結點 return h.next; }codeblocks中運行程式碼：
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; void create(Node *head) { //創建鏈表 【尾插法】 Node *temp,*p; int x; printf("請輸入鏈表元素：\n"); scanf("%d",&x); p = head; //p為尾結點 while(x != 9999) { temp = (Node *)malloc(sizeof(Node)); temp ->data = x; p ->next = temp; p = p ->next; scanf("%d",&x); } temp ->next = NULL; } void input(Node *head) { Node *p = head ->next; //p為工作指針 while(p != NULL) { printf("%d\t",p ->data); p = p ->next; } } int reverseBetween(Node *head,int m,int n) { if(n < m) return 0; if(n == m) return head; Node *pre,*p,*q,*t; int i = 1; p = head->next; pre = head; while(i < m) { pre = p; p = p->next; ++i; } t = p; //t 記錄翻轉部分的起點 if(m < n) { p = p->next; ++i; } while(i <= n) { q = p; p = p->next; ++i; q->next = pre->next; pre->next = q; // 每次將第一步找到的結點指向反轉後的頭結點 } t->next = p; //將反轉的起點next指向反轉後面的結點 return head; } int main() { Node * head; head = (Node *)malloc(sizeof(Node)); //head為頭結點 head ->data = NULL; head ->next = NULL; create(head); input(head); printf("\n逆置後：\n"); head = reverseBetween(head,2,5); input(head); }
方法二：
提交程式碼：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseBetween(struct ListNode* head, int m, int n) { if(m == n) return head; // 不用管的情況 struct ListNode h = {0, head}; //設置一個頭節點,處理m=1的情況 struct ListNode* p = &h; //指針變數賦值 struct ListNode* tail; for(int i = 1; i <= n; i++) if(i < m) // p指向第n-1個節點位置 p = p->next; else if(i == m) // tail指向第第n個節點，這個節點反轉後處在反轉部分的最後一個 tail = p->next; else { //每次將tail後面一個節點拿出來，放在item後面 struct ListNode* item = tail->next; tail->next = tail->next->next; item->next = p->next; p->next = item; } return h.next; }codeblocks中運行程式碼：
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; void create(Node *head) { //創建鏈表 【尾插法】 Node *temp,*p; int x; printf("請輸入鏈表元素：\n"); scanf("%d",&x); p = head; //p為尾結點 while(x != 9999) { temp = (Node *)malloc(sizeof(Node)); temp ->data = x; p ->next = temp; p = p ->next; scanf("%d",&x); } temp ->next = NULL; } void input(Node *head) { Node *p = head ->next; //p為工作指針 while(p != NULL) { printf("%d\t",p ->data); p = p ->next; } } int reverseBetween(Node *head,int m,int n) { if(n < m) return 0; if(m == n) return head; // 不用管的情況 struct Node* p = head,* tail; int i ; for(i = 1; i <= n; i++) if(i < m) // p指向第n-1個節點位置 p = p->next; else if(i == m) // tail指向第第n個節點，這個節點反轉後處在反轉部分的最後一個 tail = p->next; else //每次將tail後面一個節點拿出來，放在item後面 { struct Node* item = tail->next; tail->next = tail->next->next; item->next = p->next; p->next = item; } return head; } int main() { Node * head; head = (Node *)malloc(sizeof(Node)); //head為頭結點 head ->data = NULL; head ->next = NULL; create(head); input(head); printf("\n反轉後：\n"); head = reverseBetween(head,2,4); input(head); }擴展：【逆置鏈表】
例子： 1 2 3 4 5 6 —— > 6 5 4 3 2 1
方法一：
將頭結點摘下，然後從一個結點開始，依次前插入到頭結點的後面【頭插法建立鏈表】，直到最後一個結點結束為止
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; void create(Node *head) { //創建鏈表 【尾插法】 Node *temp,*p; int x; printf("請輸入鏈表元素：\n"); scanf("%d",&x); p = head; //p為尾結點 while(x != 9999) { temp = (Node *)malloc(sizeof(Node)); temp ->data = x; p ->next = temp; p = p ->next; scanf("%d",&x); } temp ->next = NULL; } void input(Node *head) { Node *p = head ->next; //p為工作指針 while(p != NULL) { printf("%d\t",p ->data); p = p ->next; } } void reverse(Node * head) { Node *p ,*r; //p為工作指針，r為p的後繼 p = head ->next; head ->next = NULL; //將頭結點的next設為NULL //依次將元素結點摘下 while(p != NULL) { r = p ->next; // 暫存p的後繼 // 將p結點插入head之後 p ->next = head ->next; head ->next = p; p = r; } } int main() { Node * head; head = (Node *)malloc(sizeof(Node)); //head為頭結點 head ->data = NULL; head ->next = NULL; create(head); input(head); printf("\n逆置後：\n"); reverse(head); input(head); }方法二：
設定三個指針：pre，p，r指向相鄰的結點
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; void create(Node *head) { //創建鏈表 【尾插法】 Node *temp,*p; int x; printf("請輸入鏈表元素：\n"); scanf("%d",&x); p = head; //p為尾結點 while(x != 9999) { temp = (Node *)malloc(sizeof(Node)); temp ->data = x; p ->next = temp; p = p ->next; scanf("%d",&x); } temp ->next = NULL; } void input(Node *head) { Node *p = head ->next; //p為工作指針 while(p != NULL) { printf("%d\t",p ->data); p = p ->next; } } void reverse(Node * head) { //將結點指針翻轉 Node *p = head ->next ,*pre,*r = p ->next; p ->next = NULL; // 處理第一個結點 while(r != NULL) // r為空，說明p為最後一個結點 pre = p; p = r; r = r ->next; p ->next = pre; // p指向前驅pre } head ->next =p; // 處理最後一個結點 } int main() { Node * head; head = (Node *)malloc(sizeof(Node)); //head為頭結點 head ->data = NULL; head ->next = NULL; create(head); input(head); printf("\n逆置後：\n"); reverse(head); input(head); }
