# Floyd Cycle Detection Algorithm的应用

https://leetcode.com/problems/find-the-duplicate-number/



# Floyd Cycle Detection Algorithm

Python代码如下(via Wikipedia):

def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0)  # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam:  # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1

# Find the position of the first repetition of length λ
mu = 0
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.

# Next, the hare and tortoise move at same speed until they agree
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1

return lam, mu


Given a linked list, determine if it has a cycle in it.

Can you solve it without using extra space?

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return false;
while(pmove&&qmove&&qmove->next){
pmove=pmove->next;
qmove=qmove->next->next;
if(pmove==qmove)
return true;
}
return false;
}
};


# 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Can you solve it without using extra space?

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
return NULL;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
if(fast==slow){
while(entry!=slow){
entry=entry->next;
slow=slow->next;
}
return entry;
}
}
return NULL;
}
};


# 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

1.You must not modify the array (assume the array is read only).

2.You must use only constant, O(1) extra space.

3.Your runtime complexity should be less than O(n2).

4.There is only one duplicate number in the array, but it could be repeated more than once.

class Solution {
public:
int findDuplicate(vector<int>& nums) {
if(nums.empty())
return 0;
int slow=nums[0],fast=nums[nums[0]];
while(slow!=fast){
slow=nums[slow];
fast=nums[nums[fast]];
}
fast=0;
while(fast!=slow){
slow=nums[slow];
fast=nums[fast];
}
return fast;
}
};



# 链表的变形

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

1.迭代:迭代的方法就是遍历整个链表，将指向下一结点的指针改变方向，要注意的是因为单链表无法直接找到某个结点的前驱，所以我们需要三个指针，用来记录当前结点，当前节点的后继和其后继的后继，代码如下:

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
cur->next=NULL;
while(pnext){
prev=pnext->next;
pnext->next=cur;
cur=pnext;
pnext=prev;
}
}
};


2.递归:

n1 → … → nk-1 → nk → nk+1 ← … ← nm


head->next-next=head;


/*Recursion*/
struct ListNode* reverseList(struct ListNode* head) {
return p;
}



# 143. 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}.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
struct ListNode * reverseList(struct ListNode *head){
cur->next=NULL;
while(pnext){
prev=pnext->next;
pnext->next=cur;
cur=pnext;
pnext=prev;
}
}
public:
return;
while(fast&&fast->next){
slow=slow->next;
fast=fast->next->next;
}

right=slow->next;
slow->next=NULL;/*从中间截断*/

right=reverseList(right);
qmove=right;
int index=0;
/*对于奇数个和偶数个要分两种情况*/
while(pmove&&qmove){
if(index%2==0){
struct ListNode * next=pmove->next;
pmove->next=qmove;
pmove=next;
}
else{
struct ListNode * next=qmove->next;
qmove->next=pmove;
qmove=next;
}
index++;
}
}
};


# 61. 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.

/**
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode* rotateRight(struct ListNode* head, int k) {
int len=1;
while(pmove->next){
pmove=pmove->next;
len++;
}
k=len-k%len;
while(k){
pmove=pmove->next;
k--;
}
pmove->next=NULL;
}


# 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

Given 1->2->3->4->5->NULL,

return 1->3->5->2->4->NULL.

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on …

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(even&&even->next){
odd->next=even->next;
odd=odd->next;
even->next=odd->next;
even=even->next;
}
}
};


# 86. 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->2and x = 3,

return 1->2->2->4->3->5.

1. 结点值小于val，放入链表1 2. 其余情况放入链表2

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
struct ListNode left(0),right(0);
struct ListNode *pLeft=&left,*pRight=&right;
pLeft=pLeft->next;
}
else{
pRight=pRight->next;
}
}
pRight->next=NULL;
pLeft->next=right.next;
return left.next;
}
};


# 24. Swap Nodes in Pairs

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.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct ListNode dummy(0);
while(ptr2){
if(!ptr2->next)
break;
struct ListNode * nextstart=ptr2->next->next;
ptr2->next->next=ptr2;
ptr1->next=ptr2->next;
ptr2->next=nextstart;
ptr1=ptr2;
ptr2=ptr2->next;
}
return dummy.next;
}
};


# 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Hint:

1.Try two pointers.

2.Did you use the property of “the order of elements can be changed”?

3.What happens when the elements to remove are rare?

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int new_len=0,i=0,size=nums.size();
for(i=0;i<nums.size();i++){
if(nums[i]!=val){
nums[new_len++]=nums[i];
}
}
return new_len;
}
};


class Solution {
public:
int removeElement(vector<int>& nums, int val) {
return distance(nums.begin(),remove(nums.begin(),nums.end(),val));
}
};


# 203. 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

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
struct ListNode dummy(0);
struct ListNode *pmove=&dummy;
while(pmove->next){
if(pmove->next->val==val)
pmove->next=pmove->next->next;
else
pmove=pmove->next;
}
return dummy.next;
}
};


# 19. 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.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
struct ListNode dummy(0);
struct ListNode * fast=&dummy,*slow=&dummy,*tmp=NULL;
for(int i=n;i>0;i--)
fast=fast->next;
while(fast->next){
fast=fast->next;
slow=slow->next;
}
tmp=slow->next;
slow->next=tmp->next;
delete tmp;
return dummy.next;
}
};


# 26.Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())
return 0;
int i=0,new_len=0;
for(i=1;i<nums.size();i++){
if(nums[i]!=nums[new_len])
nums[++new_len]=nums[i];
}
return new_len+1;
}
};


class Solution {
public:
int removeDuplicates(vector<int>& nums) {
return distance(nums.begin(),unique(nums.begin(),nums.end()));
}
};


# 80.Remove Duplicates from Sorted Array II

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice?

For example, Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn’t matter what you leave beyond the new length.

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.size()<3)
return nums.size();
int new_len=1,size=nums.size(),i=0;
for(i=2;i<size;i++){
if(nums[i]!=nums[new_len-1])
nums[++new_len]=nums[i];
}
return new_len+1;
}
};


# 83. 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.

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while(pmove){
qmove=pmove;
while(qmove->next){
if(pmove->val==qmove->next->val){
tmp=qmove->next;
qmove->next=tmp->next;
free(tmp);
}
else
qmove=qmove->next;
}
pmove=pmove->next;
}
}
};


# 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.发现当前元素和后继元素相等: 此时我们只需要按删除链表中某一元素的方法，删去后一元素即可，同时令标记值为true

2.标记值为true 此时就需要用我们的pre指针，借助其完成删除重复元素集合的首元素，删除之后，令cur指向pre的后继元素，同时令标记值为false

3.其余情况 pre，cur指针后移即可

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
struct ListNode dummy(0);
bool duplicate=false;
while(cur){
if(cur->next&&cur->val==cur->next->val){
tmp=cur->next;
cur->next=tmp->next;
free(tmp);
duplicate=true;
}
else if(duplicate){
pre->next=cur->next;
free(cur);
cur=pre->next;
duplicate=false;
}
else{
pre=cur;
cur=cur->next;
}
}
}
};



# 27.Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example: Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int new_len=0,i=0,size=nums.size();
for(i=0;i<nums.size();i++){
if(nums[i]!=val){
nums[new_len++]=nums[i];
}
}
return new_len;
}
};