leetcode Ch5-Linked List

一、

1. Remove Duplicates from Sorted List II

 1 class Solution {
 2 public:
 3     ListNode* deleteDuplicates(ListNode* head) {
 4         ListNode* dummy = new ListNode(0);
 5         dummy->next = head;
 6         ListNode* pre = dummy;
 7         ListNode* cur = head;
 8         while (cur != NULL && cur->next != NULL) {
 9             if (cur->val == cur->next->val) {
10                 while(cur->next != NULL && cur->val == cur->next->val) {
11                     cur = cur->next;            
12                 }
13                 pre->next = cur->next;
14                 cur = cur->next;
15             } else {
16                 pre = pre->next;
17                 cur = cur->next;
18             }
19         }
20         return dummy->next;
21     }
22 };

View Code

2. Remove Duplicates from Sorted List

 1 class Solution {
 2 public:
 3     ListNode* deleteDuplicates(ListNode* head) {
 4         ListNode* dummy = new ListNode(0);
 5         dummy->next = head;
 6         ListNode* pre = dummy, *cur = head;
 7         while (cur != NULL && cur->next != NULL) {
 8             if (cur->val == cur->next->val) {
 9                 while (cur->next != NULL && cur->val == cur->next->val) {
10                     cur = cur->next;
11                 }
12                 pre->next = cur;
13                 pre = pre->next;
14                 cur = cur->next;
15             } else {    
16                 cur = cur->next;
17                 pre = pre->next;
18             }    
19         }
20         return dummy->next;
21     }
22 };

View Code

只在1.的基础上改了两句。

二、

1. Reverse Linked List 【模板式】

 1 ListNode* reverseList(ListNode* head) {
 2     ListNode* prev = NULL;
 3     while (head != NULL) {
 4         ListNode* next = head->next;
 5         head->next = prev;
 6         prev = head;
 7         head = next;
 8     }
 9     return prev;
10 }

View Code

while循环里和swap很像，上一句的右侧都是下一句的左侧。

2. Reverse Linked List II

 1 class Solution {
 2 public:
 3     ListNode* reverseBetween(ListNode* head, int m, int n) {
 4         ListNode* dummy = new ListNode(0);
 5         dummy->next = head;
 6         ListNode* prev = dummy;
 7         for (int i = 1; i < m; i++) {
 8             prev = prev->next;
 9         }
10         head = prev->next;
11         ListNode* next = head->next;
12         ListNode* pprev = prev;
13         ListNode* tail = head;
14         for (int i = m; i <= n; i++) {  //这部分和reverseList一样
15             next = head->next;
16             head->next = prev;
17             prev = head;
18             head = next;
19         }
20         pprev->next = prev;
21         tail->next = head;
22         return dummy->next;
23     }
24 };

View Code

中间(m, n)区间内reverse和1.里reverseList一样。

注意：从m到n这几个元素都参与for循环了，包括第m个元素！进行reverse之后，head指向第n+1个元素，prev指向逆转后的新head（从m到n这几个元素中的新head）。

Partition List

 1 class Solution {
 2 public:
 3     ListNode* partition(ListNode* head, int x) {
 4         ListNode* leftDummy = new ListNode(0);
 5         ListNode* rightDummy = new ListNode(0);
 6         ListNode* left = leftDummy, *right = rightDummy;
 7         while (head != NULL) {
 8             if (head->val < x) {
 9                 left->next =  head;
10                 left = left->next;
11             } else {
12                 right->next = head;
13                 right = right->next;
14             }
15             head = head->next;
16         }
17         right->next = NULL;
18         left->next = rightDummy->next;
19         return leftDummy->next;
20     }
21 };

View Code

Merge Two Sorted Lists

 1 class Solution {
 2 public:
 3     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
 4         ListNode* dummy = new ListNode(0);
 5         ListNode* pre = dummy;
 6         while (l1 != NULL && l2 != NULL) {
 7             if (l1->val < l2->val) {
 8                 pre->next = l1;
 9                 l1 = l1->next;
10             } else {
11                 pre->next = l2;
12                 l2 = l2->next;
13             }
14             pre = pre->next;
15         }
16         if (l1 != NULL) {
17             pre->next = l1;
18         }
19         if (l2 != NULL) {
20             pre->next = l2;
21         }
22         return dummy->next;
23     }
24 };

View Code

Sort List

用MergeSort和QuickSort分别实现一下。

MergeSort用到了findMedian的方法（利用双指针可以达到one-pass找到中点）。

 1 class Solution {
 2 public:
 3     ListNode* findMiddle(ListNode* head) { // 找到的是下标为(n - 1) / 2的点（如果是偶数个数，那就是中间偏左一点的）
 4         ListNode* slow = head, *fast = head->next;
 5         while (fast != NULL && fast->next != NULL) {
 6             slow = slow->next;
 7             fast = fast->next->next;
 8         }
 9         return slow;
10     }
11     ListNode* merge(ListNode* l1, ListNode* l2) {
12         ListNode* dummy = new ListNode(0);
13         ListNode* pre = dummy;
14         while (l1 != NULL && l2 != NULL) {
15             if (l1->val < l2->val) {
16                 pre->next = l1;
17                 l1 = l1->next;
18             } else {
19                 pre->next = l2;
20                 l2 = l2->next;
21             }
22             pre = pre->next;
23         }
24         if (l1 != NULL) {
25             pre->next = l1;
26         }
27         if (l2 != NULL) {
28             pre->next = l2;
29         }
30         return dummy->next;
31     }
32     
33     ListNode* sortList(ListNode* head) {
34         if (head == NULL || head->next == NULL) {
35             return head;
36         }
37         ListNode* mid = findMiddle(head);    
38         ListNode* right = sortList(mid->next);
39         mid->next = NULL;
40         ListNode* left = sortList(head);
41          return merge(left, right);
42     }
43 };

View Code

其中merge即为上一题中的mergeTwoLists.

注意：findMiddle函数最开始时slow = head, fast = head->next. 通过这种方式可以保证求出来的mid是当有偶数个元素时是中间偏左一点的。

Reorder List

【三大链表基本操作：findMiddle，reverse，merge】

 1 class Solution {
 2 public:
 3     ListNode* findMiddle(ListNode* head) {
 4         ListNode* slow = head, *fast = head;
 5         while (fast != NULL && fast->next != NULL) {
 6             slow = slow->next;
 7             fast = fast->next->next;
 8         }
 9         return slow;
10     }
11     ListNode* reverseList(ListNode* head) {
12         ListNode* prev = NULL;
13         while (head != NULL) {
14             ListNode* next = head->next;
15             head->next = prev;
16             prev = head;
17             head = next;
18         }
19         return prev;
20     }
21     ListNode* merge(ListNode* l1, ListNode* l2) {
22         ListNode* dummy = new ListNode(0);    
23         ListNode* prev = dummy;
24         int count = 0;
25         while (l1 != NULL && l2 != NULL) {
26             count++;
27             if (count % 2 == 1) {
28                 prev->next = l1;
29                 l1 = l1->next;
30             } else {
31                 prev->next = l2;
32                 l2 = l2->next;
33             }
34             prev = prev->next;
35         }
36         if (l1 != NULL) {
37             prev->next = l1;
38         } else {
39             prev->next = l2;
40         }
41         return dummy->next; 
42     }
43     void reorderList(ListNode* head) {
44         if (head == NULL || head->next == NULL) {
45             return;
46         }
47         ListNode* mid = findMiddle(head);
48         ListNode* p = reverseList(mid->next);
49         mid->next = NULL;
50         merge(head, p);
51     }
52 };

View Code

Merge k Sorted Lists

方法1：利用堆（priority_queue）。每次取出K个队列中的最小值（logK），共取N次，因此复杂度为 NlogK

 1 class Solution {
 2 public:
 3     struct cmp {
 4         bool operator()(ListNode* p, ListNode* q) {
 5             return p->val > q->val;
 6         }
 7     };
 8     
 9     ListNode* mergeKLists(vector<ListNode*> &lists) {
10         if (lists.empty()) {
11             return NULL;
12         }
13         priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
14         ListNode* dummy = new ListNode(0);
15         ListNode* prev = dummy;
16         for (int i = 0; i < lists.size(); i++) {
17             if (lists[i] != NULL) {
18                 pq.push(lists[i]);
19             }
20         }
21         while (!pq.empty()) {
22             ListNode* tmp = pq.top();
23             prev->next = tmp;
24             prev = tmp;
25             pq.pop();
26             if (tmp->next != NULL) {
27                 pq.push(tmp->next);
28             }
29         }
30         return dummy->next;
31     }
32 };

View Code

方法2：分治。【自顶向下】

 1 class Solution {
 2 public:
 3     ListNode* mergeKLists(vector<ListNode*> &lists) {
 4         if (lists.empty()) {
 5             return NULL;
 6         }
 7         return mergeHelper(lists, 0, lists.size() - 1);
 8     }
 9     
10     ListNode* mergeHelper(vector<ListNode*> &lists, int start, int end) {
11         if (start == end) {
12             return lists[start];
13         }
14         int mid = start + (end - start) / 2;
15         ListNode* left = mergeHelper(lists, start, mid);
16         ListNode* right = mergeHelper(lists, mid + 1, end);
17         return mergeTwoLists(left, right);    
18     }
19     
20     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
21         ListNode* dummy = new ListNode(0);
22         ListNode* prev = dummy;
23         while (l1 != NULL && l2 != NULL) {
24             if (l1->val < l2->val) {
25                 prev->next = l1;
26                 l1 = l1->next;
27             } else {
28                 prev->next = l2;
29                 l2 = l2->next;
30             }
31             prev = prev->next;
32         }
33         if (l1 != NULL) {
34             prev->next = l1;
35         } else {
36             prev->next = l2;
37         }
38         return dummy->next;
39     }
40 };

View Code

注意：不要忘了判空！这种边界条件要谨慎！谨记！

Linked List Cycle

 1 class Solution {
 2 public:
 3     bool hasCycle(ListNode* head) {
 4         if (head == NULL) {
 5             return false;
 6         }
 7         ListNode* slow = head, *fast = head;
 8         while (fast && fast->next) {
 9             slow = slow->next;    
10             fast = fast->next->next;
11             if (slow == fast) {
12                 return true;
13             }
14         }
15         return false;
16     }
17 };

View Code

Linked List Cycle II

 1 class Solution {
 2 public:
 3     ListNode* detectCycle(ListNode* head) {
 4         ListNode* slow = head, *fast = head;
 5         while (fast && fast->next) {
 6             slow = slow->next;
 7             fast = fast->next->next;
 8             if (slow == fast) {
 9                 while (head != slow) {
10                     head = head->next;
11                     slow = slow->next;
12                 }
13                 return slow;
14             }
15         }
16         return NULL;
17     }
18 };

View Code

Copy List with Random Pointer

 1 class Solution {
 2 public:
 3     
 4     void copyNext(RandomListNode* head) {
 5         RandomListNode* pre = head;
 6         while (pre != NULL) {
 7             RandomListNode* tmp = new RandomListNode(pre->label);
 8             tmp->next = pre->next;
 9             pre->next = tmp;
10             pre = pre->next->next;
11         }
12     }
13     void copyRandom(RandomListNode* head) {
14         RandomListNode* pre = head;
15         while (pre != NULL) {
16             if (pre->random != NULL) { // don't forget
17                 pre->next->random = pre->random->next;
18             }
19             pre = pre->next->next;
20         }
21     }
22     
23     RandomListNode* splitList(RandomListNode* head) {
24         RandomListNode* newHead = head->next;
25         RandomListNode* q = newHead;
26         while (head != NULL) {
27             head->next = q->next;
28             head = head->next;
29             if (head) { // don't forget
30                 q->next = head->next;
31             }
32             q = q->next;
33         }
34         return newHead;
35     }
36     
37     RandomListNode* copyRandomList(RandomListNode* head) {
38         if (head == NULL) {
39             return NULL;
40         }
41         copyNext(head);
42         copyRandom(head);
43         return splitList(head);
44     }
45 };

View Code

注意！处理链表题很重要的一点是：在对一个指针p取next时，首先要确保 p!=NULL

Clone Graph

Convert Sorted List to Binary Search Tree

Convert Binary Tree to Doubly Linked List

Reverse Nodes in k-Group

Heapify 堆化

=================================================

24	Swap Nodes in Pairs	32.4%	Medium
148		22.2%	Medium
61	Rotate List	21.7%	Medium
25		25.4%	Hard
206		31.9%	Easy
92		26.0%	Medium
143		21.0%	Medium
19	Remove Nth Node From End of List	27.0%	Easy
203	Remove Linked List Elements	25.9%	Easy
83		34.5%	Easy
82		25.0%	Medium
86		27.4%	Medium
234	Palindrome Linked List	22.6%	Easy
21		32.6%	Easy
23		21.1%	Hard
141		36.3%	Medium
142		31.4%	Medium
160	Intersection of Two Linked Lists	28.7%	Easy
147	Insertion Sort List	26.6%	Medium
237	Delete Node in a Linked List	46.7%	Easy
138		25.2%	Hard
109		27.9%	Medium
2	Add Two Numbers	20.7%	Medium

[剑指offer] 两个链表的第一个公共节点

 1 class Solution {
 2 public:
 3     ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
 4         ListNode* p = pHead1;
 5         int count1 = 0, count2 = 0;
 6         while (p != NULL) {
 7             count1++;
 8             p = p->next;
 9         }
10         p = pHead2;
11         while (p != NULL) {
12             count2++;
13             p = p->next;
14         }
15         if (count1 < count2) {
16             return findNode(pHead1, count1, pHead2, count2);    
17         } else {
18             return findNode(pHead2, count2, pHead1, count1);
19         }
20     }
21 
22     ListNode* findNode(ListNode* pHead1, int count1, ListNode* pHead2, int count2) {
23         if (pHead1 == NULL) {
24             return NULL;
25         }
26         int tmp = count2 - count1;
27         ListNode* p2 = pHead2, *p1 = pHead1;
28         while (tmp--) {
29             p2 = p2->next;
30         }
31         while (p1 != NULL && p1 != p2) {
32             p1 = p1->next;
33             p2 = p2->next;
34         }
35         return p1;
36     }
37 };

View Code

参考剑指offer P193. 本题说的“公共节点”不是指“值相等”，而是“同一个节点”。即两链表在该点处汇合。