转载

LeetCode OJ Linked List: 21题、2题、141题和142题

21题：Merge Two Sorted Lists

题目分析：实在没啥分析了。

 1 class Solution {  2 public:  3     ListNode* mergeTwoLists(ListNode *l1, ListNode *l2)  4     {  5         if (l1 == NULL)  6         {  7             return l2;  8         }  9      10         if (l2 == NULL) 11         { 12             return l1; 13         } 14      15         ListNode tmpNode(-1); 16         ListNode *p = &tmpNode; 17      18         while (l1 != NULL && l2 != NULL) 19         { 20             if (l1->val <= l2->val) 21             { 22                 p->next = l1; 23                 l1 = l1->next; 24             } 25             else 26             { 27                 p->next = l2; 28                 l2 = l2->next; 29             } 30             p = p->next; 31         } 32      33         p->next = l1 != NULL ? l1 : l2; 34         return tmpNode.next; 35     } 36 };

View Code

2题：Add Two Numbers

题目分析：如果你选择重新建立链表，那是比较简单的。如果你选择利用已有结点，并且建立部分结点，那么你就要考虑一下边界了，比如两个链表一样长，一个长一个短。

单独创建一个链表：

 1 class Solution {  2 public:  3     ListNode* addTwoNumbers(ListNode *l1, ListNode *l2)  4     {  5         if (l1 == NULL)  6         {  7             return l2;  8         }  9         if (l2 == NULL) 10         { 11             return l1; 12         } 13      14         int carrbit = 0; 15         ListNode tmpNode(-1); 16         ListNode *pre = &tmpNode; 17      18         for (ListNode *p = l1, *q = l2; p != NULL || q != NULL 19             ; p = p == NULL ? p : p->next, q = q == NULL ? q : q->next, pre = pre->next) 20         { 21             int a = p != NULL ? p->val : 0; 22             int b = q != NULL ? q->val : 0; 23      24             pre->next = new ListNode((a + b + carrbit) % 10); 25             carrbit = (a + b + carrbit) / 10; 26         } 27      28         if (carrbit > 0) 29         { 30             pre->next = new ListNode(carrbit); 31         } 32      33         return tmpNode.next; 34     } 35 };

View Code

利用部分已有结点：

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

View Code

141题：Linked List Cycle

LeetCode OJ Linked List: 21题、2题、141题和142题

题目分析： 快指针走两步，慢指针走一步，相遇则有环，遇到NULL，则无环。这个问题就是费脑筋的龟兔赛跑问题，算法是Floyd's cycle-finding algorithm，详细说明，可以参考 http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare 。我第一次遇到这样的问题时，有个疑问，为什么快指针走两步，慢指针走一步呢？快指针走3步，4步，慢指针走1步成不成呢？答案是：取决于环的长度。假设环的长度为2，快指针走3步，慢指针走1步。那么将来在环里，可能会出现不相遇情况。

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

View Code

142题：Linked List Cycle II

LeetCode OJ Linked List: 21题、2题、141题和142题

题目分析：当快慢指针相遇时距离环的入口点距离为k，此时让慢指针指向表头，快指针位置不变，快慢指针每次走一步，相遇点就是入口点。证明，可以参考 http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work ，说的非常详细了。

 1 class Solution {  2 public:  3     ListNode* detectCycle(ListNode *head)  4     {  5         if (head == NULL || head->next == NULL)  6         {  7             return NULL;  8         }  9      10         ListNode *slow = head, *fast = head; 11         while (fast != NULL && fast->next != NULL) 12         { 13             fast = fast->next->next; 14             slow = slow->next; 15             if (slow == fast) 16             { 17                 break; 18             } 19         } 20         if (fast == NULL || fast->next == NULL) 21         { 22             return NULL; 23         } 24      25         slow = head; 26         while (slow != fast) 27         { 28             slow = slow->next; 29             fast = fast->next; 30         } 31      32         return slow; 33     } 34 };