[剑指 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/