剑指Offer（三十六）：两个链表的第一个公共结点

2018年1月15日10:53:09 4 9,214 °C
摘要

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

剑指Offer（三十六）：两个链表的第一个公共结点

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

这道题和160.Intersection of Two Linked Lists是一样的。都是求两个链表的第一个公共结点。

公共结点的样子：

剑指Offer（三十六）：两个链表的第一个公共结点

上图就是一个有公共结点的例子，在公共结点之后，两个链表指针指向的地址是相同的。

这道题有两个解法。

方法一：

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

方法二：

我们也可以先让把长的链表的头砍掉，让两个链表长度相同，这样，同时遍历也能找到公共结点。此时，时间复杂度O(m+n)，空间复杂度为O(MAX(m,n))。

2、代码

C++：

这里使用方法二。

C++
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        // 如果有一个链表为空，则返回结果为空
        if(pHead1 == NULL || pHead2 == NULL){
            return NULL;
        }
        // 获得两个链表的长度
        unsigned int len1 = GetListLength(pHead1);
        unsigned int len2 = GetListLength(pHead2);
        // 默认 pHead1 长， pHead2短，如果不是，再更改
        ListNode* pHeadLong = pHead1;
        ListNode* pHeadShort = pHead2;
        int LengthDif = len1 - len2;
        // 如果 pHead1 比 pHead2 小
        if(len1 < len2){
            ListNode* pHeadLong = pHead2;
            ListNode* pHeadShort = pHead1;
            int LengthDif = len2 - len1;
        }
        // 将长链表的前面部分去掉，使两个链表等长
        for(int i = 0; i < LengthDif; i++){
            pHeadLong = pHeadLong->next;
        }
        
        while(pHeadLong != NULL && pHeadShort != NULL && pHeadLong != pHeadShort){
            pHeadLong = pHeadLong->next;
            pHeadShort = pHeadShort->next;
        }
        return pHeadLong;
    }
private:
    // 获得链表长度
    unsigned int GetListLength(ListNode* pHead){
        if(pHead == NULL){
            return 0;
        }
        unsigned int length = 1;
        while(pHead->next != NULL){
            pHead = pHead->next;
            length++;
        }
        return length;
    }
};

Python：

这里使用方法一：

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if pHead1 == None or pHead2 == None:
            return None
        cur1, cur2 = pHead1, pHead2
        while cur1 != cur2:
            cur1 = cur1.next if cur1 != None else pHead2
            cur2 = cur2.next if cur2 != None else pHead1
        return cur1

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：4   其中：访客  3   博主  1

    • avatar yyx 来自天朝的朋友 火狐浏览器 Ubuntu Linux 北京市 电信 2
      回复 2019年8月23日 上午11:13  沙发

      请问python里cur1, cur2 = pHead1, pHead2是连接操作吗～

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
          回复 2019年8月26日 上午9:50  1层

          @yyx 这个是赋值，可以分开写,cur1=pHead1,cur2=pHead2

        • avatar zymize 来自天朝的朋友 搜狗浏览器 Windows 10 黑龙江省哈尔滨市 电信 1
          回复 2020年4月25日 上午9:36  板凳

          请问如果python用思路二写应该怎么写，您这里python用思路一比思路二简洁吗？

          • avatar 小白 来自天朝的朋友 谷歌浏览器 Windows 10 广东省广州市 联通 1
            回复 2021年2月22日 上午9:37  地板

            python3.* 解法,你看看能行不？：
            方法1：
            a = [6,2,3,5]
            b = [4,3,7]
            c,d = min(a,b),max(a,b)
            print(c)
            print(d)
            for x in c:
            if x in d:
            res = c.index(x)
            break
            if res == None:
            print(‘没有公共结点’)
            else:
            print(res,c[res])