剑指Offer 36. 两个链表的第一个公共结点（链表）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目描述

输入两个链表，找出它们的第一个公共结点。

题目地址

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

思路

思路1：把两个链表拼接起来，一个pHead1在前pHead2在后，一个pHead2在前pHead1在后，这样，生成了两个相同长度的链表，我们只要同时遍历这两个表，就一定能找到公共节点。时间复杂度O(m+n)，空间复杂度O(m+n).

思路2：首先依次遍历两个链表，记录两个链表的长度m和n，如果 m > n，那么我们就先让长度为m的链表走m-n个结点，然后两个链表同时遍历，当遍历到相同的结点的时候停止即可。对于 m < n，同理。

Python

# -*- coding:utf-8 -*-

class ListNode:

    def __init__(self, x):

        self.val = x

        self.next = None

node1 = ListNode(1)

node2 = ListNode(2)

node3 = ListNode(3)

node4 = ListNode(4)

node5 = ListNode(5)

node6 = ListNode(6)

node1.next = node2

node2.next = node5

node5.next = node6

node3.next = node4

node4.next = node5

class Solution:

    def FindFirstCommonNode(self, pHead1, pHead2):

        # 方法1

        # if not pHead1 or not pHead2:

        #     return None

        # cur1, cur2 = pHead1, pHead2

        # while cur1 != cur2:

        #     cur1 = cur1.next if cur1 else pHead2

        #     cur2 = cur2.next if cur2 else pHead1

        # return cur1

        # 方法2

        if not pHead1 or not pHead2:

            return None

        m = n = 0

        cur1, cur2 = pHead1, pHead2

        while cur1:

            m += 1

            cur1 = cur1.next

        while cur2:

            n += 1

            cur2 = cur2.next

        if m > n:

            for i in range(m-n):

                pHead1 = pHead1.next

            while pHead1:

                if pHead1 == pHead2:

                    return pHead1

                pHead1, pHead2 = pHead1.next, pHead2.next

        else:

            for i in range(n-m):

                pHead2 = pHead2.next

            while pHead1:

                if pHead1 == pHead2:

                    return pHead1

                pHead1, pHead2 = pHead1.next, pHead2.next

        return None

if __name__ == '__main__':

    result = Solution().FindFirstCommonNode(node1, node3)

    while result:

        print(result.val, end = ' ')

        result = result.next