每日一题《剑指offer》链表篇之两个链表的第一个公共节点

终有救赎

发布于 2023-12-14 14:10:41

1830

发布于 2023-12-14 14:10:41

文章被收录于专栏：多线程

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

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

难度：中等

描述

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

数据范围

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

举例

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

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

## 解题思路

方法一:双指针长度比较法如果两个链表有公共节点，那么它们后半部分都是相同的，我们要找的也就是后半部分的第一个节点。链表前半部分不同，长度也可能不同，因此同时遍历的话不一定就会同时到达第一个公共节点。

但是，如果我们能够找到长度差：

int n = p1 - p2;

较长的链表指针先走n步：

//假设pHead1更长
for(int i = 0; i < n; i++)
    pHead1 = pHead1.next;

然后两个指针分别走剩余的步数，就会同时到达第一个公共节点。

具体做法：

step 1：单独的遍历两个链表，得到各自的长度。
step 2：求得两链表的长度差nnn，其中较长的链表的指针从头先走nnn步。
step 3：两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共节点。

方法二:双指针连接法由上种方法长度差的思路，不同于上述一个指针先走另一个指针后走，仅需将两个链表连在一起，两个指针同步走。

p1 = p1 == NULL ? pHead2 : p1->next;   
p2 = p2 == NULL ? pHead1 : p2->next;

易知将两个链表连在一起长度都相等，对于遍历两个链表的两个指针，公共部分走的步数是一样的，非公共部分因都走了两个链表，因此也是相同的，所以绕了一圈，第一个相同的节点便是第一个公共节点。

具体做法：

step 1：判断链表情况，其中有一个为空，则不能有公共节点，返回null。
step 2：两个链表都从表头开始同步依次遍历。
step 3：不需要物理上将两个链表连在一起，仅需指针在一个链表的尾部时直接跳到另一个链表的头部。
step 4：根据上述说法，第一个相同的节点便是第一个公共节点。

实现代码（java）

方法一:

public class Solution {
    //计算链表长度的函数
    public int ListLenth(ListNode pHead){  
        ListNode p = pHead;
        int n = 0;
        while(p != null){
            n++;
            p = p.next;
        }
        return n;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int p1 = ListLenth(pHead1);  
        int p2 = ListLenth(pHead2);
        //当链表1更长时，链表1指针先走p1-p2步
        if(p1 >= p2){  
            int n = p1 - p2;
            for(int i = 0; i < n; i++){
                pHead1 = pHead1.next;
            }
            //两个链表同时移动，直到有公共节点时停下
            while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){ 
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        //反之，则链表2先行p2-p1步
        else{  
            int n = p2 - p1;
            for(int i = 0; i < n; i++){
                pHead2 = pHead2.next;
            }
            //两个链表同时移动，直到有公共节点时停下
            while((pHead1 != null) && (pHead2 != null) && (pHead1 != pHead2)){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        return pHead1;
    }
}

方法二:

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //其中有一个为空，则不能有公共节点，返回null
        if(pHead1 == null || pHead2 == null) 
            return null;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        //相当于遍历两次两个链表所有值
        while(p1 != p2){ 
            p1 = p1 == null ? pHead2 : p1.next;   
            p2 = p2 == null ? pHead1 : p2.next;
        }
        return p1;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-14，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历