Question

link

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.

Credits:
Special thanks to @stellari for adding this problem and creating all test cases.

            <div id="tags" class="btn btn-xs btn-warning">Show Tags</div>
            <span class="hide">
              
              <a class="btn btn-xs btn-primary" href="/tag/linked-list/">Linked List</a>
              
            </span>
          
        </div>

Analysis

This question is very similar to [LeetCode Plus] Lowest Common Ancestor of Binary Tree (II).

Solution

This is a pretty nice answer. The following explanation is quoted from g4g:

  1. Get count of the nodes in first list, let count be c1.

  2. Get count of the nodes in second list, let count be c2.

  3. Get the difference of counts d = abs(c1 – c2)

  4. Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.

  5. Then we can traverse both the lists in parallel till we come across a common node.

Code

/**
 * 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) {
        return helper(headA, headB, length(headA) - length(headB));
    }

    public ListNode helper(ListNode n1, ListNode n2, int offset) {
        if (offset < 0) {
            return helper(n2, n1, 0 - offset);
        }
        // move n1 to the distance of offset
        while (offset != 0) {
            n1 = n1.next;
            offset--;
        }
        while (n1 != null && n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    int length(ListNode node) {
        int len = 0;
        while (node != null) {
            node = node.next;
            len++;
        }
        return len;
    }
}