LeetCode OJ Linked List: 92題、143題、147題和160題，leetcodeoj
92題：Reverse Linked List II
題目分析：第一種思路：找到m的前驅和n的後繼，記錄下來，將m至n斷開，逆置後，再重新連接上。第二種思路：將m至n重新插入到m的前驅後面。小心邊界。
第一種思路：
![]()
1 class Solution {
2 public:
3 ListNode* reverseList(ListNode *head)
4 {
5 if (head == NULL || head->next == NULL)
6 {
7 return head;
8 }
9
10 ListNode *cur = head, *pre = NULL, *next = head->next;
11 for (; cur != NULL; pre = cur, cur = next, next = next ? next->next : NULL)
12 {
13 cur->next = pre;
14 }
15
16 return pre;
17 }
18
19 ListNode* reverseBetween(ListNode *head, int m, int n)
20 {
21 if (head == NULL || head->next == NULL || m == n)
22 {
23 return head;
24 }
25
26 ListNode tmpNode(-1);
27 tmpNode.next = head;
28
29 int k = 1;
30 ListNode *prem = &tmpNode, *curm = head;
31 ListNode *curn = head, *nextn = curn->next;
32 for (; k < m; ++k)
33 {
34 prem = curm;
35 curm = curm->next;
36 curn = curn->next;
37 }
38 for (; k < n; ++k)
39 {
40 curn = curn->next;
41 }
42 nextn = curn->next;
43
44
45 curn->next = NULL;
46 ListNode *tmp = reverseList(curm);
47 prem->next = tmp;
48 curm->next = nextn;
49
50 return tmpNode.next;
51 }
52 };
View Code
第二種思路：
![]()
1 class Solution
2 {
3 public:
4 ListNode *reverseBetween(ListNode *head, int m, int n)
5 {
6 ListNode dummy(-1);
7 dummy.next = head;
8 ListNode *prev = &dummy;
9 for (int i = 0; i < m - 1; ++i)
10 {
11 prev = prev->next;
12 }
13
14 ListNode* const head2 = prev;
15 prev = head2->next;
16 ListNode *cur = prev->next;
17 for (int i = m; i < n; ++i)
18 {
19 prev->next = cur->next;
20 cur->next = head2->next;
21 head2->next = cur; // 頭插法
22 cur = prev->next;
23 }
24
25 return dummy.next;
26 }
27 };
View Code
143題：Reorder List
題目分析：從中間分割，第二段逆置，然後與第一段交替插入。
View Code
147題：Insertion Sort List
題目分析：直接插入排序，簡單粗暴。
View Code
160題：Intersection of Two Linked Lists
題目分析：k=長鏈表長度-短鏈表長度，然後長鏈表先走k步，長短鏈表一起走，直到相交。
View Code
LeetCode OJ 其它題目：
LeetCode OJ Linked List: 24題、148題和61題
