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

发表于

描述

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

输入描述：

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数 FindFirstCommonNode 里面，用户得到的输入只有 pHead1 和 pHead2 。

返回值描述：

返回传入的 pHead1 和 pHead2 的第一个公共结点，后台会打印以该节点为头节点的链表。

示例1

1
2
3
4
输入:  {1,2,3},{4,5},{6,7}
返回:  {6,7}
说明:  第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

示例2

1
2
3
输入:  {1},{2,3},{}
返回:  {}
说明:  2个链表没有公共节点 ,返回null，后台打印{}

题解

使用两个指针 a，b 分别指向两个链表 pHead1 ， pHead2 的头结点，然后同时分别逐结点遍历，当 a 到达链表 pHead1 的末尾时，重新定位到链表 pHead2 的头结点；当 b 到达链表 pHead2 的末尾时，重新定位到链表 pHead1 的头结点。当双指针相遇时，所指向的结点就是第一个公共结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
package main

type ListNode struct{
    Val int
    Next *ListNode
}


/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
*/
func FindFirstCommonNode( pHead1 *ListNode ,  pHead2 *ListNode ) *ListNode {
    // write code here
    cur1 := pHead1
    cur2 := pHead2

    for cur1 != cur2 {
        if cur1 == nil {
            cur1 = pHead2
        } else {
            cur1 = cur1.Next
        }

        if cur2 == nil {
            cur2 = pHead1
        } else {
            cur2 = cur2.Next
        }
    }

    return cur1
}