Intersection of Two Linked Lists

Posted on | In , |

看到非常聪明的解法，跟用两个指针判断链表是否存在环有点相同的思想（不想仔细想有什么相同的，只不过有这直觉），当然记录下来，跪倒在天才的脑洞下。

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

For example, the following two linked lists:

1
2
3
4
5
A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

I found most solutions here preprocess linkedlists to get the difference in len.
Actually we don’t care about the “value” of difference, we just want to make sure two pointers reach the intersection node at the same time.

We can use two iterations to do that. In the first iteration, we will reset the pointer of one linkedlist to the head of another linkedlist after it reaches the tail node. In the second iteration, we will move two pointers until they points to the same node. Our operations in first iteration will help us counteract the difference. So if two linkedlist intersects, the meeting point in second iteration must be the intersection point. If the two linked lists have no intersection at all, then the meeting pointer in second iteration must be the tail node of both lists, which is null

Below is my commented Java code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
>     //boundary check
>     if(headA == null || headB == null) return null;
>     
>     ListNode a = headA;
>     ListNode b = headB;
>     
>     //if a & b have different len, then we will stop the loop after second iteration
>     while( a != b){
>     	//for the end of first iteration, we just reset the pointer to the head of another linkedlist
>         a = a == null? headB : a.next;
>         b = b == null? headA : b.next;    
>     }
>     
>     return a;
> }
>

假设A的长度为a+c，B的长度为b+c，指针a走完A的长度再走B一遍，一共走了a+c+b+c，指针b走完B的长度再走了一遍A的长度，一共走了b+c+a+c，于是两个指针a和b必然会在第二遍的公共节点c处相遇。

单单一个机智我觉得已经无法形容了。