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

目录

描述

输入描述

返回值描述 

示例1 

 示例2

思路

代码

 

---

描述

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

例如输入{1,2,3},{4,5},{6,7}时两个无环的单向链表的结构如下图所示 

可以看到它们的第一个公共结点的结点值为6所以返回结点值为6的结点。

输入描述

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

返回值描述 

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

示例1 

输入 

{1,2,3},{4,5},{6,7}

返回值

{6,7}

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

 示例2

输入

{1},{2,3},{}

返回值

{}

 说明2个链表没有公共节点 ,返回null后台打印{}

思路

这种思路谁能想得到也算是双指针每次还是需要多用双指针去思考思考

使用两个指针N1,N2一个从链表1的头节点开始遍历我们记为N1一个从链表2的头节点开始遍历我们记为N2。

让N1和N2一起遍历当N1先走完链表1的尽头为null的时候则从链表2的头节点继续遍历同样如果N2先走完了链表2的尽头则从链表1的头节点继续遍历也就是说N1和N2都会遍历链表1和链表2。

因为两个指针同样的速度走完同样长度链表1+链表2不管两条链表有无相同节点都能够到达同时到达终点。

N1最后肯定能到达链表2的终点N2肯定能到达链表1的终点。

所以如何得到公共节点

• 有公共节点的时候N1和N2必会相遇因为长度一样嘛速度也一定必会走到相同的地方的所以当两者相等的时候则会第一个公共的节点
• 无公共节点的时候此时N1和N2则都会走到终点那么他们此时都是null所以也算是相等了。

代码

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        ListNode l1 = pHead1;
        ListNode l2 = pHead2;

        while (l1 != l2) {
            l1 = l1 != null ? l1.next : pHead2;
            l2 = l2 != null ? l2.next : pHead1;
        }
        return l1;
    }