tsanmmmm2000's Tech Blog

Question

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.

Thinking

從討論區中發現一個蠻有技巧的解法，要知道兩個Linked List是否有交集，我們只要判斷兩個Node的記憶體位址是否一樣。主要邏輯是讓兩個Linked List從頭開始走訪，當其中一方走到尾端，便再從另一方的頭開始走訪，它們碰頭的Node，即是交點，因為理論上兩方走的距離會是一樣的，若沒有交集，最終也會一起走向尾端

My C# Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        var tempA = headA;
        var tempB = headB;
        while(tempA != tempB)
        {
            tempA = (tempA != null) ? tempA.next : headB;
            tempB = (tempB != null) ? tempB.next : headA;
        }
        return tempA;
    }
}