约瑟夫环问题

来源：Bloomberg Onsite

原帖：http://blog.csdn.net/wuzhekai1985/article/details/6628491

题目：
最近看bloomberg的面经看到出现过几次约瑟夫环问题。这道题的模拟解法非常直观，更好的解法是观察索引的映射关系采用recursion来解。以前没有仔细思考过这个问题。博客链接给了很好的解释。

约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。  稍微简化一下。

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

代码：
1] Brute force solution

 int JosephusProblem(int n, int m) {   
   if (n < 1 || m < 1)   
     return -1;   
    
   list<int> listInt;   
   unsigned i;   
   //初始化链表   
   for (i = 0; i < n; i++)   
     listInt.push_back(i);    
   list<int>::iterator iterCurrent = listInt.begin();   
   while (listInt.size() > 1) {   
     //前进m - 1步   
     for(i = 0; i < m-1; i++) {   
       if(++iterCurrent == listInt.end())   
         iterCurrent = listInt.begin();   
     }   
     //临时保存删除的结点   
     list<int>::iterator iterDel = iterCurrent;   
     if(++iterCurrent == listInt.end())   
       iterCurrent = listInt.begin();   
     //删除结点   
     listInt.erase(iterDel);   
   }  
   return *iterCurrent;   
 }  

2] dp solution

 int JosephusProblem(int n, int m) {   
   if(n < 1 || m < 1)   
     return -1;   
   vector<int> f(n+1,0);   
   for(unsigned i = 2; i <= n; i++)   
     f[i] = (f[i-1] + m) % i;    
   return f[n];   
 }  

160 Intersection of Two Linked Lists

来源：Leetcode

原帖：https://leetcode.com/problems/intersection-of-two-linked-lists/

题目：
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
 A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗          
 B:     b1 → b2 → b3
begin to intersect at node c1.

Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

代码：

 class Solution {  
 public:  
   ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {  
     ListNode *p1 = headA, *p2 = headB;  
     if (!p1 || !p2) return NULL;  
     while (p1 && p2 && p1 != p2) {  
       p1 = p1->next;  
       p2 = p2->next;  
       if (p1 == p2) return p1;  
       if (!p1) p1 = headB;  
       if (!p2) p2 = headA;  
     }  
     return p1;  
   }  
 };  

203 Remove Linked List Elements

来源：Leetcode

原帖：https://leetcode.com/problems/remove-linked-list-elements/

题目：
Remove all elements from a linked list of integers that have value val.
Example
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   ListNode* removeElements(ListNode* head, int val) {  
     ListNode dummy(0);  
     dummy.next = head;  
     ListNode* cur = &dummy;  
     while (cur->next) {  
       if (cur->next->val == val) {  
         ListNode* del = cur->next;  
         cur->next = cur->next->next;  
         delete del;  
       } else {  
         cur = cur->next;  
       }  
     }  
     return dummy.next;  
   }  
 };  

Convert Sorted List to Binary Search Tree

来源：Leetcode

原帖：https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/

题目：
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 /**  
  * Definition for binary tree  
  * struct TreeNode {  
  *   int val;  
  *   TreeNode *left;  
  *   TreeNode *right;  
  *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   int getLength(ListNode *head) {  
     int length = 0;  
     while (head) {  
       length++;  
       head = head->next;  
     }  
     return length;  
   }  
   
   TreeNode *sortedListToBSTHelper(ListNode* &head, int length) {  
     if (length == 0) return NULL;  
     TreeNode* left = sortedListToBSTHelper(head, length / 2);  
     TreeNode* root = new TreeNode(head->val);  
     head = head->next; // move head pointer!  
     TreeNode* right = sortedListToBSTHelper(head, length - length / 2 - 1);  
     root->left = left;  
     root->right = right;    
     return root;  
   }  
   
   TreeNode *sortedListToBST(ListNode *head) {  
     return sortedListToBSTHelper(head, getLength(head));  
   }  
 };  

Palindrome In Linked List

来源：EPI, Facebook Onsite

原帖：EPI 4.10

题目：
Write a function that determines whether a sequence represented by a singly linked list L is a palindrome. Assume L can be changed and does not have to be restored it to its original state.

代码：
1] Iteration

 // 1 -> 2 -> 2 -> 1  
 // 1 -> 2 -> 3 -> 2 -> 1  
 struct ListNode {  
     int val;  
     ListNode* next;  
     ListNode(int v) : val(v), next(NULL) {}  
 };  
   
 // Iteration  
 bool isPalindrome(ListNode* L) {  
     // Find the middle point of L  
     ListNode* slow = L, *fast = L;  
     while (fast) {  
         fast = fast->next;  
         if (fast) {  
             fast = fast->next;  
             slow = slow->next;  
         }  
     }  
     // Compare the first half and reverse second half lists  
     ListNode* reverse = reverse_linked_list(slow);  
     while (reverse && L) {  
         if (reverse->date != L->data) {  
             return false;  
         }  
         reverse = reverse->next;  
         L = L->next;  
     }  
     return true;  
 }  

2] Recursion

 bool isPalindrome(ListNode* L) {  
     ListNode* left = L, *right = L;  
     return isPalindrome(left, right);  
 }   
   
 bool isPalindrome(ListNode* &left, ListNode* right) {  
     if (!right) return true;  
     if (!isPalindrome(left, right->next)) return false;  
     if (left->val != right->next) return false;  
     left = left->next;  
     return true;  
 }  

Reorder List

来源：Leetcode

原帖：http://oj.leetcode.com/problems/reorder-list/

题目：
Given a singly linked list L: L0->L1->...->Ln-1->Ln, reorder it to: L0->Ln->L1->Ln-1->L2->Ln-2->... You must do this in-place without altering the nodes' values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
Solution: Reverse the back half first, then reorder.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;   
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode* getMiddle(ListNode *head) {  
         ListNode *slow = head;  
         ListNode *fast = head->next;  
         while (fast && fast->next) {  
             fast = fast->next->next;  
             slow = slow->next;  
         }  
         return slow;  
     }  
   
     ListNode* reverse(ListNode* head) {  
         ListNode dummy(0);  
         dummy.next = head;  
         while (head->next) {  
             ListNode* mov = head->next;  
             head->next = mov->next;  
             mov->next = dummy.next;  
             dummy.next = mov;  
         }  
         return dummy.next;  
     }  
   
     void reorderList(ListNode *head) {  
         if (!head || !head->next) return;  
         // move the middle of the list  
         ListNode* mid = getMiddle(head);  
         // reverse the second half lists  
         ListNode* right = mid->next;  
         mid->next = NULL;  
         right = reverse(right);  
         // merge from the list  
         ListNode* left = head;  
         while (left && right) {   
             ListNode* node1 = left->next;  
             ListNode* node2 = right->next;  
             left->next = right;  
             right->next = node1;  
             left = node1;  
             right = node2;  
         }  
     }  
 };  

Reverse Nodes in K-Group

来源：Leetcode

原帖：http://oj.leetcode.com/problems/reverse-nodes-in-k-group/

题目：
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed. Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5

代码：

 /**  
 * Definition for singly-linked list.  
 * struct ListNode {  
 *   int val;  
 *   ListNode *next;  
 *   ListNode(int x) : val(x), next(NULL) {}  
 * };  
 */  
 class Solution {  
 public:  
     int getLength(ListNode *head) {  
         int length = 0;  
         while (head) {  
             head = head->next;  
             length++;  
         }  
         return length;  
     }  
   
     ListNode *reverseKGroup(ListNode *head, int k) {  
         if (k <= 1) return head;  
         int reverseTimes = getLength(head) / k;  
         ListNode dummy(0);   
         dummy.next = head;  
         head = &dummy;  
         ListNode *cur = head->next;      
         while (reverseTimes--) {  
             for (int i = 0; i < k - 1; ++i) {  
                 ListNode *move = cur->next;  
                 cur->next = move->next;  
                 move->next = head->next;  
                 head->next = move;  
             }  
             head = cur;  
             cur = head->next;  
         }  
         return dummy.next;  
     }  
 };  

Swap Nodes in Pairs

来源：Leetcode

原帖：http://oj.leetcode.com/problems/swap-nodes-in-pairs/

题目：
Given a linked list, swap every two adjacent nodes and return its head.
For example, Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
Solution: 1. Iterative solution with constant space.
                2. Recursive solution with O(n) space (for practice).

代码：
1] Iteration

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     //Iteration  
     ListNode *swapPairs(ListNode *head) {  
         ListNode dummy(0);  
         dummy.next = head;  
         ListNode *cur = &dummy;  
         while (cur->next && cur->next->next) {  
             ListNode *move = cur->next->next;  
             cur->next->next = move->next;  
             move->next = cur->next;  
             cur->next = move;  
             cur = move->next;  
         }  
         return dummy.next;  
     }  
 };  

2] Recursion

 class Solution {  
 public:   
     //Recursion  
     ListNode *swapPairs(ListNode *head) {  
         if (!head || !head->next) return head;  
         ListNode *first = head, *second = head->next;  
         first->next = second->next;  
         second->next = first;  
         first->next = swapPairs(first->next);  
         return second;  
     }  
 };  

Rotate List

来源：Leetcode

原帖：http://oj.leetcode.com/problems/rotate-list/

题目：
Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
Solution: Notice that k can be larger than the list size (k % list_size). This solution traverses the list twice at most.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *rotateRight(ListNode *head, int k) {  
         if (!head) return NULL;  
         ListNode* tail = head;  
         int length = 1;  
         while (tail->next) {  
             tail = tail->next;  
             length++;  
         }  
         k = k % length; // edge case: the list rotates more than one round.  
         if (k == 0) return head;  
         ListNode* cur = head;  
         for (int i = 0; i < length - k - 1; i++) {  
             cur = cur->next;        
         }  
         ListNode* newHead = cur->next;  
         cur->next = NULL;  
         tail->next = head;  
         return newHead;  
     }  
 };  

Remove Nth Node From End of List

来源：Leetcode

原帖：http://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/

题目：
Given a linked list, remove the nth node from the end of list and return its head. For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid. Try to do this in one pass.
Solution: head---back------front------>NULL
                   |          |
                   ---> n <----

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *removeNthFromEnd(ListNode *head, int n) {  
         // corner case: 头结点,使用dummy node  
         ListNode dummy(0);  
         ListNode* back = &dummy;  
         ListNode* front = &dummy;      
         dummy.next = head;  
         while (n--) {  
             front = front->next;  
         }  
         while (front->next) {  
             front = front->next;  
             back = back->next;  
         }  
         ListNode *node = back->next;  
         back->next = node->next;  
         delete node;  
         return dummy.next;  
     }  
 };  

Remove Duplicates from Sorted List II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

题目：
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

代码：
1] iteration

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:    
     ListNode *deleteDuplicates(ListNode *head) {  
         if (!head || !head->next) return head;      
         ListNode dummy(0);  
         dummy.next = head;  
         head = &dummy;   
         while (head->next && head->next->next) {  
             if (head->next->val == head->next->next->val) {  
                 int val = head->next->val;  
                 while (head->next && head->next->val == val) {  
                     ListNode* node = head->next;  
                     head->next = head->next->next;  
                     delete node;  
                 }        
             } else {  
                 head = head->next;  
             }  
         }  
         return dummy.next;  
     }  
 };  

2] recursion

 class Solution {  
 public:  
     ListNode *deleteDuplicates(ListNode *head) {  
         if (!head) {  
             return NULL;  
         }  
         if (!head->next || head->val != head->next->val) {  
             head->next = deleteDuplicates(head->next);  
             return head;  
         }  
         int val = head->val;  
         while (head && head->val == val) {  
             ListNode *temp = head;  
             head = head->next;  
             delete temp;  
         }      
         return deleteDuplicates(head);  
     }  
 };  

Remove Duplicates from Sorted List I

来源：Leetcode

原帖：http://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

题目：
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   
 class Solution {  
 public:  
     ListNode *deleteDuplicates(ListNode *head) {  
         if (!head || !head->next) {  
             return head;  
         }  
         ListNode *cur = head;  
         while (cur->next) {  
             if (cur->val == cur->next->val) {  
                 ListNode *node = cur->next;  
                 cur->next = node->next;  
                 delete node;  
             } else {  
                 cur = cur->next;  
             }  
         }  
         return head;  
     }  
 };  

Reverse Linked List II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/reverse-linked-list-ii/

题目：
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 <= m <= n <= length of list.

代码：

 class Solution {  
 public:  
     ListNode *reverseBetween(ListNode *head, int m, int n) {  
         ListNode dummy(0);  
         dummy.next = head;  
         head = &dummy;    
         for (int i = 0; i < m - 1; ++i) {  
             head = head->next;  
         }  
         ListNode *cur = head->next;  
         for (int i = 0; i < n - m; ++i) {  
             ListNode *move = cur->next;  
             cur->next = move->next;  
             move->next = head->next;  
             head->next = move;  
         }  
         return dummy.next;  
     }  
 };  

Partition List

来源：Leetcode

原帖：http://oj.leetcode.com/problems/partition-list/

问题：
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *partition(ListNode *head, int x) {  
         if (!head) return NULL;  
         ListNode leftDummy(0);  
         ListNode rightDummy(0);  
         ListNode *left = &leftDummy, *right = &rightDummy;  
         while (head) {  
             if (head->val < x) {  
                 left->next = head;  
                 left = head;  
             } else {  
                 right->next = head;  
                 right = head;  
             }  
             head = head->next;  
         }  
         right->next = NULL;  
         left->next = rightDummy.next;  
         return leftDummy.next;  
     }  
 };  

206 Reverse Linked List I

来源：Leetcode

原帖：https://leetcode.com/problems/reverse-linked-list/

题目：
Given a linear time non-recursive function that reverses a singly linked list. The function should use no more than constant storage beyond that needed for the list itself.

代码：

 struct ListNode {  
     int val;  
     ListNode* next;  
     ListNode(int v) : val(v), next(NULL) {}  
 };  
   
 //Recursion  
 ListNode* reverse_linked_list(ListNode* head) {  
     if (!head || !head->next) {  
         return head;  
     }  
     ListNode* new_head = reverse_linked_list(head->next);  
     head->next->next = head;  
     head->next = NULL;  
     return new_head;  
 }  
   
 //Iteration  
 ListNode* reverse_linked_list(ListNode* head) {  
     if (!head) return NULL;  
     ListNode* newhead = head;  
     while (head->next) {  
         ListNode* n = head->next;  
         head->next = n->next;  
         n->next = newhead;  
         newhead = n;  
     }  
     return newhead;  
 }  
   

Sort List (Insert Sort)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/insertion-sort-list/

题目：
Sort a linked list using insertion sort.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *insertionSortList(ListNode *head) {  
         if(!head) return NULL;  
         ListNode dummy(0); // 1->2->5->null insert 3;     
         while (head) { // head: insert linked list node  
             ListNode* node = &dummy;  
             while (node->next != NULL && node->next->val <= head->val) {  
                 node = node->next;  
             }       
             ListNode* temp = head->next;  
             head->next = node->next;  
             node->next = head;  
             head = temp;  
         }  
         return dummy.next;  
     }  
 };  

Sort List (Merge Sort)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sort-list/

题目：
Sort a linked list in O(nlogn) time using constant space complexity.

代码：1] 考虑merge sort

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
 class Solution {  
 public:  
     int getLength(ListNode *head) {  
         int length = 0;  
         while (head) {  
             length++;  
             head = head->next;  
         }  
         return length;  
     }  
   
     ListNode* mergeList(ListNode *head1, ListNode *head2) {  
         ListNode dummy(0);   
         ListNode *cur = &dummy;  
         while (head1 && head2) {  
             ListNode **min = head1->val < head2->val ? &head1 : &head2;  
             cur->next = *min;  
             cur = cur->next;  
             *min = (*min)->next;  
         }  
         if (!head1) cur->next = head2;  
         if (!head2) cur->next = head1;  
         return dummy.next;  
     }  
   
     ListNode* sortLinkedList(ListNode* &head, int N) {  
         if (N == 0) return NULL;  
         if (N == 1) {  
             ListNode* cur = head;  
             head = head->next; // update head pointer  
             cur->next = NULL; // end of list  
             return cur;  
         }  
         int half = N / 2;  
         ListNode* head1 = sortLinkedList(head, half);  
         ListNode* head2 = sortLinkedList(head, N - half);  
         return mergeList(head1, head2);  
     }  
   
     ListNode *sortList(ListNode *head) {  
         return sortLinkedList(head, getLength(head));  
     }  
 };  

Merge Two Sorted Lists

来源：Leetcode

原帖：http://oj.leetcode.com/problems/merge-two-sorted-lists/

题目：
Merge two sorted linked lists and return it as a new list.
The new list should be made by splicing together the nodes of the first two lists.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   
 class Solution {  
 public:  
     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {  
         ListNode dummy(0);  
         ListNode *cur = &dummy;  
         while (l1 && l2) {  
             if (l1->val <= l2->val) {  
                 cur->next = l1;  
                 l1 = l1->next;  
             } else {  
                 cur->next = l2;  
                 l2 = l2->next;  
             }  
             cur = cur->next;  
         }  
         cur->next = l1 != NULL ? l1 : l2;  
         return dummy.next;  
     }  
 };  

Merge K Sorted Lists

来源：Leetcode

原帖：http://oj.leetcode.com/problems/merge-k-sorted-lists/

题目：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
 class compare {  
 public:  
     bool operator() (ListNode* left, ListNode* right) { // min-heap  
         return left->val > right->val;  
     }  
 };  
   
 class Solution {  
 public:  
     ListNode *mergeKLists(vector<ListNode *> &lists) {  
         if (lists.empty()) return NULL;      
         priority_queue<ListNode*, vector<ListNode*>, compare> heap;  
         for (int i = 0; i < lists.size(); i++) {  
             if (lists[i]) {  
                 heap.push(lists[i]);  
             }  
         }  
         ListNode dummy(0);  
         ListNode* tail = &dummy;  
         while(!heap.empty()) {  
             tail->next = heap.top();   
             heap.pop();  
             tail = tail->next;  
             if(tail->next) {  
                 heap.push(tail->next);  
             }  
         }  
         return dummy.next;  
     }  
 };  

Linked List Cycle II

来源：Leetcode

原帖：http://oj.leetcode.com/problems/linked-list-cycle-ii/

题目：
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
如果fast pointer是slow pointer的2倍，可以找到相遇点
但是如果fast pointer不是slow pointer的2倍，不能保证一定相遇。

Note:
k: linkedlist length out of cycle
n: cycle length
s: any x times speed
p, q: any integers

n - ((s-1)k % n) + p * n = (s-1) * q
n * (p+1) = (s-1) * q + (s-1) * k % n

s = 3, k = 3, n = 5
5 * (p+1) = 2*q + 1
n * (p+1) = 2 * q + 2 * k % n

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *detectCycle(ListNode *head) {  
         if (!head || !head->next) return NULL;  
         // {1,2}, tail connects to node {1}, if fast = head->next(不能使用)  
         ListNode *slow = head;  
         ListNode *fast = head;   
         while (fast && fast->next) { // assume cycle exists  
             fast = fast->next->next;  
             slow = slow->next;  
             if (fast == slow) break;  
         }  
         if (slow != fast) {  
             return NULL; // no cycle  
         }  
         fast = head;  
         while (fast != slow) {  
             fast = fast->next;  
             slow = slow->next;  
         }    
         return slow;  
     }  
 };