pua我

面试题 02.07. 链表相交

题意是给出两个链表，得出相加的起始结点,

1.利用头指针遍历链表，先得出各自的链表长度

2.再次初始化头指针，不然会报空指针异常

3.将两个头指针尾对齐

4.怎么得出他们相交呢？ 令他们相等，后面的结点也在比较，如果不相等，那就接着循环下一个结点

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *  val = x; *  next = null; *     } * } */public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode cura = headA; ListNode curb = headB; int na = 0 ,nb = 0; while(cura != null){     cura = cura.next;     na++; } while(curb!= null){     curb = curb.next;     nb++; } //再次初始化cura和curb cura = headA; curb = headB; if(nb>na){     while(nb-->na){  curb = curb.next;     } }else{     while(na -->nb){  cura = cura.next;     } } while(cura !=null){     if(cura ==curb){  return cura;     }     cura = cura.next;     curb = curb.next; } return null; }}

142. 环形链表 II

双指针法

思路

这道题目，不仅考察对链表的操作，而且还需要一些数学运算。

主要考察两知识点：

• 判断链表是否环
• 如果有环，如何找到这个环的入口

判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

那么来看一下，为什么fast指针和slow指针一定会相遇呢？

可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。

会发现最终都是这种情况， 如下图：

fast和slow各自再走一步， fast和slow就相遇了

这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

如果有环，如何找到这个环的入口

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：(x + y) * 2 = x + y + n (y + z)

整理公式之后为如下公式：x = (n - 1) (y + z) + z

注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

n =1，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

总结：

1. fast=2slow （快指针每次2步，路程刚好2倍）
2. fast= slow + nz (相遇时，刚好多走了n圈）

推出：s = nz

从head结点走到入环点需要走 ： x + nz， 而slow已经走了nz，那么slow再走x步就是入环点了。

如何知道slow刚好走了x步？ 从head开始，和slow指针一起走，相遇时刚好就是x步

/** * Definition for singly-linked list. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *  val = x; *  next = null; *     } * } */public class Solution {    public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null &&fast.next != null){     fast = fast.next.next;     slow = slow.next;     if(fast == slow){  ListNode index1 = head;  ListNode index2 = fast;  while(index1 != index2){      index1  = index1.next;      index2 =  index2.next;  }  return index2;     }      } return null;    }}

笑话娱乐网站