相交链表和环形链表

（一）相交链表

相交链表

思路：先分别计算出A列表和B列表的长度，判断它们的尾节点是否相等，如果不相等就不相交，直接返回空。然后让两个列表中的长的列表先走它们的差距步，然后再一起走，第一次相等的点就为交点。 留意要用所在判断是否相交。

1. /**
2. * Definition for singly-linked list.
3. * struct ListNode {
4. *     int val;
5. *     struct ListNode *next;
6. * };
7. */
8. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
9.     struct ListNode *curA = headA, *curB = headB;
10.     int lenA = 1, lenB = 1;
12.     //计算链表长度
13.     while(curA->next)
14.     {
15.         curA = curA->next;
16.         ++lenA;
17.     }
18.     while(curB->next)
19.     {
20.         curB = curB->next;
21.         ++lenB;
22.     }
24.     //判断尾节点是否相交,不相交就不相交
25.     if(curA != curB)
26.     {
27.         return NULL;
28.     }
29.    
30.     //长的先走差距步
31.     //假设A列表较长
32.     int gap = abs(lenA - lenB);
33.     struct ListNode *longlist = headA, *shortlist = headB;
34.     if(lenB > lenA)
35.     {
36.         longlist = headB;
37.         shortlist = headA;
38.     }
39.     while(gap--)
40.     {
41.         longlist = longlist->next;
42.     }
44.     while(longlist != shortlist)
45.     {
46.         longlist = longlist->next;
47.         shortlist = shortlist->next;
48.     }
50.     return shortlist;
51. }

复制代码

（二）环形链表（一）

环形链表

链表的末了一个节点的下一个指针指向链表中的某个非空节点，形成一个闭环，叫环形链表。
如何判断一个链表是否有环：
   1、创建一个快指针，一个慢指针指向链表的头节点head
  2、让快指针一次向后移动两个节点，慢指针一次向后移动一个节点。

1. struct ListNode* slow = head,*fast = head;
2.     while (fast && fast->next)
3.     {
4.         slow = slow->next;
5.         fast = fast->next->next;
6.         if(slow == fast)
7.         return true;
8.     }
9.     return false;

复制代码

 为什么循环结束条件是fast && fast->fast
 当链表中有环时，fast和fast->next永世不会指向NULL；
当链表中无环时，①fast移动两次后，刚好指向NULL，结束循环；②fast移动一次后就已经指向NULL，在进行移动，就是对NULL的解引用

（三）环形链表 二

环形链表 II

 题目的意思是说：判断链表是否有环，有环则返回入环点，没有则返回NULL。

假设链表从头到入环点的距离为a，环的巨细为c，slow和fast相遇时slow走的距离为b，那么有下面的式子：
 

所以，记载一个指针ptr指向链表头部，一个指针meet指向slow和fast相遇的位置，让prt和meet一起走，它们两个相遇就是入环点。

1. struct ListNode *detectCycle(struct ListNode *head) {
2.     struct ListNode* slow = head,*fast = head;
3.     while(fast && fast->next)
4.     {
5.         slow = slow->next;
6.         fast = fast->next->next;
7.         if(slow == fast)
8.         {
9.             struct ListNode* meet = slow;
10.             struct ListNode* ptr = head;
11.             while(meet != ptr)
12.             {
13.                 meet = meet->next;
14.                 ptr = ptr->next;
15.             }
16.             return meet;
17.         }
18.     }
19.     return NULL;
20. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

继续阅读请点击广告