160. 相交链表

image.png

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  12.         ListNode* p = headA, * q = headB;
  13.         while(p != q)
  14.         {
  15.             p = p ? p->next : headB;
  16.             q = q ? q->next : headA; 
  17.         }
  18.         return p;
  19.     }
  20. };

142. 环形链表 II

  1. 判断链表是否有环

快慢指针，快指针走2步，慢指针走1步
若能相遇则有环，快指针走x+y+n(y+z),慢指针走x+y
为什么慢指针不走**x+y+m(y+z)**?
slow在环入口时，fast在环的任意位置，假设在距离环入口k位置；
相遇时fast走2k,slow走k，由于kimage.png
image.png
链表 - 图4

  1. 找到环的入口

快=2慢
=> x+y+n(y+z)=2(x+y)
=> x = (n-1)(y+z)+z
index1、index2分别从头节点、相遇点同时出发分别经过x, z，在环入口相遇
链表 - 图5