剑指offer-题37：两个链表的第一个公共节点

超、凢脫俗 2022-05-27 02:40 126阅读 0赞

## **题目描述** ##

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

实验平台：[牛客网][Link 1]

--------------------

## **解决思路：** ##

这题书上列举了两个可行的解法，分别如下

**解法一**：

![这里写图片描述][70]

**解法二**：

![这里写图片描述][70 1]  
![这里写图片描述][70 2]

其中解法二我是用java实现的，解法一我用python3实现。跟解法二相比，解法一需要另外两个列表当做栈，相当于用空间换了时间。具体代码如下

java:

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
    public class Solution {
        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
            int list1Length = getListLength(pHead1);
            int list2Length = getListLength(pHead2);
            ListNode longList = null;
            ListNode shortList = null;
            int diff;
            if (list1Length >= list2Length) {
                longList = pHead1;
                shortList = pHead2;
                diff = list1Length - list2Length;
            } else {
                longList = pHead2;
                shortList = pHead2;
                diff = list2Length - list1Length;
            }
    
            for (int i = 0; i < diff; i++) {
                longList = longList.next;
            }
    
            while (longList != null && shortList != null & longList != shortList) {
                longList = longList.next;
                shortList = shortList.next;
            }
    
            if (longList == shortList) {
                return longList;
            } else {
                return null;
            }
        }
    
        public int getListLength(ListNode node) {
            int length = 0;
            while (node != null) {
                length++;
                node = node.next;
            }
            return length;
        }
    }

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
            stack1 = []
            stack2 = []
            common_node = None
            while pHead1 is not None:
                stack1.append(pHead1)
                pHead1 = pHead1.next
            while pHead2 is not None:
                stack2.append(pHead2)
                pHead2 = pHead2.next
            while len(stack1) > 0 and len(stack2) > 0 and stack1[-1] == stack2[-1]:
                common_node = stack1[-1]
                stack1.pop()
                stack2.pop()
            return common_node

[Link 1]: https://www.nowcoder.com/ta/coding-interviews?page=1
[70]: /images/20220527/c70236a0b96f4a0e9e9cee3c809680e9.png
[70 1]: /images/20220527/18bf363289424c8bbe4d94d7b2278a9d.png
[70 2]: /images/20220527/ce08a0a3f99a4a9b97703e2058242154.png