First Common Node of Two Linked Lists

1. Problem Description

Given two linked lists, find their first common node. (Note: because the input data is provided as linked lists, invalid test data may be displayed in other ways; the input data is guaranteed to be valid.)

2. Approach

• Two pointers

3. Implementation

3.1. Two Pointers

• java

public class 两个链表的第一个公共结点
{
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2)
    {
        // Check parameters
        if (pHead1 == null || pHead2 == null)
        {
            return null;
        }
        // Traverse the two linked lists first to get their lengths
        int len1 = 0;
        int len2 = 0;
        ListNode current1 = pHead1;
        ListNode current2 = pHead2;
        while (current1 != null)
        {
            len1++;
            current1 = current1.next;
        }
        while (current2 != null)
        {
            len2++;
            current2 = current2.next;
        }
        // Let the longer list advance by the length difference first
        current1 = pHead1;
        current2 = pHead2;
        if (len2 > len1)
        {
            int step = len2 - len1;
            for (int i = 0; i < step; i++)
            {
                current2 = current2.next;
            }
        }
        else
        {
            int step = len1 - len2;
            for (int i = 0; i < step; i++)
            {
                current1 = current1.next;
            }
        }
        // Move both together
        while (current1 != current2)
        {
            current1 = current1.next;
            current2 = current2.next;
        }

        return current1;
    }
}

• go

// Two-pointer method
// Time complexity: O(m+n), where m and n are the lengths of linked lists A and B. In the worst case, the common node is the last node and m+n nodes need to be traversed
// Space complexity: O(1)
func FindFirstCommonNode(pHead1 *ListNode, pHead2 *ListNode) *ListNode {
	n1 := pHead1
	n2 := pHead2

	count1 := 0
	count2 := 0
	for n1 != nil {
		count1++
		n1 = n1.Next
	}
	for n2 != nil {
		count2++
		n2 = n2.Next
	}

	n1 = pHead1
	n2 = pHead2
	if count2 > count1 {
		diff := count2 - count1
		for i := 0; i < diff; i++ {
			n2 = n2.Next
		}
	} else {
		diff := count1 - count2
		for i := 0; i < diff; i++ {
			n1 = n1.Next
		}
	}

	for n1 != n2 && n1 != nil {
		n1 = n1.Next
		n2 = n2.Next
	}

	return n1

}

4. References

• First Common Node of Two Linked Lists - NowCoder
• LCR 171. Training Plan V - LeetCode