Intersection of Two Linked Lists

Intersection of Two Linked Lists

 

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

Naive Way: 对每一A node, 遍历一遍B node,看是否交汇。这样的算法复杂度是O(n^2)。
但是题目要求了O(n) ，说明就一定存在O(n)的解法。链表有一个重要的特性就是有指针。
这些指针可以被灵活使用，这里让我想起了Populating Next Right Pointers in Each Node II里那个把next指针指向父节点的人，当时这个做法一下子直接打破了常规的想法，让指针不再局限于它的名字，我们其实也可以将left 和 right指向父节点什么的，这种约定俗成的变量名造成了先入为主的思维，往往会限制我们的想法。

那么看来要实现O(n)就必须利用好这些指针了，但是这道题不同于树，每一个节点只有一个指针，如果我们改变某一个指针，就断掉了，就无法修复了。所以我们不能断掉这些指针，但仍可以在不断掉整个链的情况下改变这些指针。

一开始我的想法是交叉A 链表和B链表的指针，看能不能弄出些名堂，但是无论怎么交叉，都只是将A和B前面的部分增长变短，问题就变成了对一个长度不同的A,B链表求交汇点。所以这样的尝试是失败的。

其实有一个节点的指针是一直没有用的，就是最后一个节点的指针，连接它到任意一个位置都改变了整个链表的结构，没错，增加了一个圈。这时才发现题目中的Notes是在给提示，前面有做过用龟兔赛跑的办法求圈的起始位置的题目，这里就可以用上了。当把尾部节点的指针链接至任意一个链表的开头，就变成一个含圈链表求圈起始位置的题目。而龟兔赛跑的算法复杂度正好是O(n)。具体龟兔赛跑是怎么回事，这里有一个比较好的教程Detecting a Loop in Singly Linked List - Tortoise & Hare

这道题是自己想出来的，还是比较开心。
/**
 * 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) {
        // edge case
        if(headA == null || headB == null){return null;}
        // connect list A into a circle
        ListNode temp = headA;
        while(temp.next != null){
            temp = temp.next;
        }
        temp.next = headA;
        // find the start node of the circle
        ListNode hare = headB;
        ListNode tortoise = headB;
        while(true){
            // hare step 2 forward
            if(hare.next != null){
                hare = hare.next;
                if(hare.next != null){
                    hare = hare.next;
                }else{
                    temp.next = null;
                    return null;
                }
            }else{
                temp.next = null;
                return null;
            }
            // tortoise step 1 forward
            if(tortoise.next != null){
                tortoise = tortoise.next;
            }else{
                temp.next = null;
                return null;
            }
            // check if they meet
            if(hare == tortoise){
                break;
            }
        }
        hare = headB;
        while(hare != tortoise){
            hare = hare.next;
            tortoise = tortoise.next;
        }
        // break list A into singly list
        temp.next = null;
       
        return hare;
    }
}