《leetCode》：Linked List Cycle II

本文主要是介绍《leetCode》：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.Follow up:
Can you solve it without using extra space?

题目大意：若链表中存在环，则找到链表中环的起点。如果没有环，返回NULL；

思路

有了上篇博文的思路，这个题就比较简单了。
思路:先用两个指针来进行遍历判断是否有环 ,一个只移动一个节点，一个移动两个节点；
如果没有环，输出NULL即可。如果有环，则断开环，将其转化为求两个链表的第一个公共节点问题

// struct ListNode {
//       int val;
//       struct ListNode *next;
//   };
int length_list(struct ListNode *head){ struct ListNode *cur=head;int len=0;while(cur){len++;cur=cur->next;}return len;
}
struct ListNode *detectCycle(struct ListNode *head) {if(head==NULL||head->next==NULL)  return NULL;struct ListNode *oneStep=head;struct ListNode *twoStep=head->next ;while(oneStep!=twoStep){if(twoStep==NULL||twoStep->next==NULL||oneStep==NULL) return NULL;else{oneStep=oneStep->next;twoStep=twoStep->next->next;}}//如果运行到这里，就说明链表中有环出现//第一步：断开环，将其转化为两个链表struct ListNode *head1=oneStep->next;oneStep->next=NULL;//第二步：求两个链表的第一个公共节点//先求两个链表的长度int len1=length_list(head);int len2=length_list(head1); //将较长的链表移动abs(len1-len2)个长度struct ListNode *lengthList=head;struct ListNode *lowList=head1; int dif=abs(len1-len2);if(len1<len2){lengthList=head1;lowList=head;}struct ListNode *cur1=lengthList;struct ListNode *cur2=lowList;while(dif>0){cur1=cur1->next;dif--;}while(cur1&&cur2){if(cur1==cur2){return cur1;}cur1=cur1->next;cur2=cur2->next;}return NULL;
}