1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 52 题] “两个链表的第一个公共结点”做题记录

[剑指 Offer 第 2 版第 52 题] “两个链表的第一个公共结点”做题记录

第 52 题:两个链表的第一个公共结点

传送门:两个链表的第一个公共结点牛客网 online judge 地址

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

样例:

给出两个链表如下所示: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B:b1 → b2 → b3 输出第一个公共节点 c1。

思路1:两个链表如果有相同起点的话就好办了,所以首先要计算出两个链表的长度,进而计算它们的差值。

Python 代码:

  class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None


    class Solution(object):

        def __get_list_node_size(self, root):
            node = root
            size = 0
            while node:
                size += 1
                node = node.next
            return size

        def findFirstCommonNode(self, headA, headB):
            """
            :type headA, headB: ListNode
            :rtype: ListNode
            """
            if headA is None or headB is None:
                return None

            s1 = self.__get_list_node_size(headA)
            s2 = self.__get_list_node_size(headB)

            # 我们默认 l1 >= l2
            h1 = headA
            h2 = headB

            if s2 > s1:
                # 如果 B 长度更长,把二者交换
                h1 = headB
                h2 = headA
            # 现在 h1 上走 (s1 - s2) 这么多长度
            for _ in range(abs(s1 - s2)):
                h1 = h1.next
            # 然后齐头并进
            while h1 and h2 and h1.val != h2.val:
                h1 = h1.next
                h2 = h2.next

            # 走到这里,如果是因为 h1 和 h2 都空了,返回 Node
            if h1 is None and h2 is None:
                return None
            else:
                return h1

Java 代码:


class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; } @Override public String toString() { StringBuilder s = new StringBuilder(); ListNode cur = this; while (cur != null) { s.append(cur.val + " -> "); cur = cur.next; } s.append("NULL"); return s.toString(); } } // 第 52 题:两个链表的第 1 个公共节点 P253 // 参考资料: // 1、https://blog.csdn.net/derrantcm/article/details/46761093 public class Solution { public static ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1 = pHead1; ListNode p2 = pHead2; while (p1 != p2) { p1 = (p1 != null ? p1.next : pHead2); p2 = (p2 != null ? p2.next : pHead1); } return p1; } }

思路2:用两个栈。

Python 代码:写法上要注意,不要想当然

  class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None


    class Solution(object):

        def findFirstCommonNode(self, headA, headB):
            """
            :type headA, headB: ListNode
            :rtype: ListNode
            """
            if headA is None or headB is None:
                return None
            stack1 = []
            stack2 = []
            node1 = headA
            while node1:
                stack1.append(node1)
                node1 = node1.next
            node2 = headB
            while node2:
                stack2.append(node2)
                node2 = node2.next
            # 注意:这里有陷阱,一定要先设置一个 result 结点
            # 如果两个链表没有公共元素,res 不会被赋值
            res = None
            while stack1 and stack2:
                node1 = stack1.pop()
                node2 = stack2.pop()
                if node1.val == node2.val:
                    # 这里暂存一下,最后一个相等的结点才是我们求的
                    res = node1
                    continue
                if stack1 is None or stack2 is None:
                    return None
            return res

思路3:拼成一样长,这个写法记住就可以了。

Python 代码:

  class Solution(object):

        def findFirstCommonNode(self, headA, headB):
            """
            :type headA, headB: ListNode
            :rtype: ListNode
            """
            if headA is None or headB is None:
                return None
            p1 = headA
            p2 = headB

            while p1 != p2:
                if p1 is None:
                    p1 = headB
                else:
                    p1 = p1.next
                if p2 is None:
                    p2 = headA
                else:
                    p2 = p2.next
            return p1

LeetCode 第 160 题:两个单链表相交的起始节点

把不整齐的地方补整理,答案也是固定写法,多写几遍。

Python 代码:

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None

    # 思路:两个链表不一样长,就想办法让它们一样长。

    class Solution(object):
        def getIntersectionNode(self, headA, headB):
            """
            :type head1, head1: ListNode
            :rtype: ListNode
            """
            if headA is None or headB is None:
                return None
            node1 = headA
            node2 = headB
            while node1 != node2:
                if node1:
                    node1 = node1.next
                else:
                    node1 = headB
                if node2:
                    node2 = node2.next
                else:
                    node2 = headA
            return node1

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 52 题] “两个链表的第一个公共结点”做题记录

链接:https://www.javajike.com/article/3297.html

« [剑指 Offer 第 2 版第 51 题] “数组中的逆序对”做题记录
[剑指 Offer 第 2 版第 53 题] “在排序数组中查找数字”做题记录»

相关推荐

QR code