160. Intersection of Two Linked Lists (E)

https://leetcode.com/problems/intersection-of-two-linked-lists/

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.

• listA - The first linked list.

• listB - The second linked list.

• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.

• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

Solution:

Version 1:

这个题前提是两个都没有环。

给你输入两个链表的头结点 headA 和 headB，这两个链表可能存在相交。

如果相交，你的算法应该返回相交的那个节点；如果没相交，则返回 null。

比如题目给我们举的例子，如果输入的两个链表如下图：

那么我们的算法应该返回 c1 这个节点。

这个题直接的想法可能是用 HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间。

如果不用额外的空间，只使用两个指针，你如何做呢？

难点在于，由于两条链表的长度可能不同，两条链表之间的节点无法对应：

如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。

解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

那你可能会问，如果说两个链表没有相交点，是否能够正确的返回 null 呢？

这个逻辑可以覆盖这种情况的，相当于 c1 节点是 null 空指针嘛，可以正确返回 null。

按照这个思路，可以写出如下代码：

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // p1 指向 A 链表头结点，p2 指向 B 链表头结点
    ListNode p1 = headA, p2 = headB;
    while (p1 != p2) {
        // p1 走一步，如果走到 A 链表末尾，转到 B 链表
        if (p1 == null) p1 = headB;
        else            p1 = p1.next;
        // p2 走一步，如果走到 B 链表末尾，转到 A 链表
        if (p2 == null) p2 = headA;
        else            p2 = p2.next;
    }
    return p1;
}

这样，这道题就解决了，空间复杂度为 O(1)，时间复杂度为 O(N)。

Version 2:

求出 L1 L2的长度,若L1<L2,用fast slow分别从头部开始走，L2先走（L2-L1）步，然后在一起走，直到相遇.

 public class Solution { 
   public ListNode getIntersectionNode(ListNode headA, ListNode headB) 
   { 
        if(headA==null || headB==null) { return null; }     
        int lenA=getlen(headA);
        int lenB=getlen(headB);
        
        
        //the longer minus the difference
        if(lenA>lenB)
        {
      	  while(lenA>lenB)
      	  {
      		  headA=headA.next;
      		  lenA--;
      	  }	    	  
        }
        else
        {
      	  while(lenB>lenA)
      	  {
      		  headB=headB.next;
      		  lenB--;
      	  }
        }
        
        
        while(headA!=null)
        {
      	  if(headA==headB)
      	  {
      		  return headA;
      	  }
      	  headA=headA.next;
      	  headB=headB.next;
        }
        
        return null;
        	      
        
   }
   
   public int getlen(ListNode head)
   {
  	 if(head==null)
  	 {
  		 return 0;
  	 }
  	 
  	 int len=0;
  	 while(head!=null)
  	 {
  		 len++;
  		 head=head.next;
  	 }
  	 return len;
   }
 }
 
 
 //寻找两条链表的交点」的核心在于让 p1 和 p2 两个指针能够同时到达相交节点 c1，
 //那么可以通过预先计算两条链表的长度来做到这一点
 class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0, lenB = 0;
        // 计算两条链表的长度
        for (ListNode p1 = headA; p1 != null; p1 = p1.next) {
            lenA++;
        }
        for (ListNode p2 = headB; p2 != null; p2 = p2.next) {
            lenB++;
        }
        // 让 p1 和 p2 到达尾部的距离相同
        ListNode p1 = headA, p2 = headB;
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                p1 = p1.next;
            }
        } else {
            for (int i = 0; i < lenB - lenA; i++) {
                p2 = p2.next;
            }
        }
        // 看两个指针是否会相同，p1 == p2 时有两种情况：
        // 1、要么是两条链表不相交，他俩同时走到尾部空指针
        // 2、要么是两条链表相交，他俩走到两条链表的相交点
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}