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

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

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

描述

代码语言：javascript复制

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

数据范围： n le 1000n≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

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

代码语言：javascript复制

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

示例

代码语言：javascript复制

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

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

代码语言：javascript复制

方法一：
我们可以把两个链表拼接起来，一个pHead1在前pHead2在后，一个pHead2在前pHead1在后
这样，生成了两个相同长度的链表，那么我们只要同时遍历这两个表，就一定能找到公共结点
时间复杂度O(m n)，空间复杂度O(m n)
方法二：
我们也可以先让把长的链表的头砍掉，让两个链表长度相同，这样，同时遍历也能找到公共结点
此时，时间复杂度O(m n)，空间复杂度为O(MAX(m,n))

代码语言：javascript复制

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {//下面所述的z为公共节点
public://(x z y)=(y z x)把两个链表弄成一样长，相等即是有第一个公共节点(效果类似于把长链表的长的部分给去掉)
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode *l1 = pHead1;
        ListNode *l2 = pHead2;
        while (l1 != l2) {//判断是否相等，不相等就循环，当两个指针都指空也是一种相等，也会跳出循环
            l1 = l1 ? l1->next : pHead2;//当前节点是否够用，不够即指向另一个链表
            l2 = l2 ? l2->next : pHead1;
        }// l1 = l1.next if l1 else l2 <-python代码
        return l1;
    }
};

代码语言：javascript复制

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        l1,l2 = pHead1,pHead2
        while l1 != l2:
            l1 = l1.next if l1 else pHead2
            l2 = l2.next if l2 else pHead1
        return l1

链表

0 人点赞