【剑指Offer】036——两个链表的第一个公共结点（链表）

题目描述

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

解题思路

如果两个链表存在公共结点，那么它们从公共结点开始一直到链表的结尾都是一样的，因此我们只需要从链表的结尾开始，往前搜索，找到最后一个相同的结点即可。但是题目给出的单向链表，我们只能从前向后搜索，这时，我们就可以借助栈来完成。先把两个链表依次装到两个栈中，然后比较两个栈的栈顶结点是否相同，如果相同则出栈，如果不同，那最后相同的结点就是我们要的返回值。
还有一种方法，不需要借助栈。先找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走，直到找到第一个公共结点。

file

参考代码

Java

import java.util.Stack;
class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    // 方法1
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        // 将两个链表入栈
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while ( pHead1 != null){
            s1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null){
            s2.push(pHead2);
            pHead2 = pHead2.next;
        }
        ListNode res = null; // 结果res
        // 弹出，最后保存的就是最先交叉的地方
        while (!s1.isEmpty() && !s2.isEmpty() && s1.peek() == s2.peek()){
            s1.pop();
            res = s2.pop();
        }
        return res;
    }
    public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) return  null;
        int count1 = 1, count2 = 1;
        ListNode p1 = pHead1; // 保存头
        ListNode p2 = pHead2;
        // 计算pHead1的长度
        while (p1.next != null){
            count1 ++;
            p1 = p1.next;
        }
        // 计算pHead2的长度
        while (p2.next != null){
            count2 ++;
            p2 = p2.next;
        }
        if (count1 > count2){
            int dif = count1 - count2;
            while (dif != 0){
                pHead1 = pHead1.next;
                dif --;
            }
        }else {
            int dif = count2 - count1;
            while (dif != 0){
                pHead2 = pHead2.next;
                dif --;
            }
        }
        while (pHead1 != null && pHead2 != null){
            if (pHead1 == pHead2){
                return pHead1;
            }
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return  null;
    }
}

Python

# -*- 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
        s1, s2 = [], []
        while pHead1:
            s1.append(pHead1)
            pHead1 = pHead1.next
        while pHead2:
            s2.append(pHead2)
            pHead2 = pHead2.next
        res = None
        while len(s1) > 0 and len(s2) > 0 and s1[-1] == s2[-1]:
            s1.pop()
            res = s2.pop()
        return res

个人订阅号

image