本文主要是介绍《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;
}
AC结果如下:
这篇关于《leetCode》:Linked List Cycle II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!