两个链表的第一个公共结点

1. 题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

2. 思路

• 双指针

3. 实现

3.1. 双指针

• java

public class 两个链表的第一个公共结点
{
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2)
    {
        //检查参数
        if (pHead1 == null || pHead2 == null)
        {
            return null;
        }
        //先遍历两个链表，获取各自的长度
        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;
        }
        //长的一方先走差值步
        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;
            }
        }
        //两个一起走
        while (current1 != current2)
        {
            current1 = current1.next;
            current2 = current2.next;
        }

        return current1;
    }
}

• go

// 双指针法
//时间复杂度：O(m+n), m，n分别为链表A，B的长度，最坏情况下，公共结点为最后一个，需要遍历m+n个结点
//空间复杂度：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. 参考

• 两个链表的第一个公共结点_牛客网
• LCR 171. 训练计划 V - 力扣（LeetCode）