链表相交

链表相交

面试题 02.07. 链表相交 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

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
        """
        p = ListNode(next = headA)
        q = ListNode(next = headB)
        lista = []
        listb = []
        while p.next != None:
            lista.append(p.next.val)
            p = p.next
        while q.next != None:
            listb.append(q.next.val)
            q = q.next
        
        index_0 = 0
        index_1 = 0
        for i in range(len(lista)):
            if lista[i] in listb:
                j = 0
                while lista[i] in listb[j+1:]:
                    j = listb[j+1:].index(lista[i])
                    index_0 = i
                    index_1 = j
                    fp = headA
                    fq = headB
                    while index_0:
                        fp = fp.next
                        index_0 -= 1
                    while index_1:
                        fq = fq.next
                        index_1 -= 1
                    if fp == fq:
                        head1 = fp
                        return head1
        return None

解二：

# 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
        """
        p = ListNode(next = headA)
        q = ListNode(next = headB)
        num1 = num2 = 0
        while p.next != None:
            p = p.next
            num1 += 1
        while q.next != None:
            q = q.next
            num2 += 1
        k = num1 - num2
        p = ListNode(next = headA)
        q = ListNode(next = headB)
        if k > 0:
            while k:
                p = p.next
                k -= 1
        else:
            while k:
                q = q.next
                k += 1
        while p.next != None:
            if p.next == q.next:
                head1 = p.next
                return head1
            p = p.next
            q = q.next
        return None

笔记

1. 解一暴力解法，逐个遍历，将两个链表val存在列表中，找到两个链表重叠元素的位置（这两个节点不一定相交，因为next不一定相同），之后判断对应链点是否相同

   值得注意的是，这种解法需要对一些特殊情况进行处理，比如在相交节点前，某一链表有一个val相同的节点，而另一个链表相交节点前没有val相同的节点，例如：

   链表1：[4,1,8,4,5]、链表2：[8,0,1,8,4,5]，相交节点为第一个链表的2号和第二个链表的3号；

   但由于链表2的0号也是8，在与链表1的2号一起判断后未通过，会导致链表1的2号被错误地遍历过去，针对此情况，可以在加一个循环 while lista[i] in listb[j+1:]（此情况leetcode未检查出来，加循环后又会超出时间限制）；

2. 解二使用了双指针法的思想，当两个链表交叉，那么相交节点后的链表是一样的，因此可以让较长链表上的指针移动到与较短链表首端对应的位置，之后依次后移，判断对应链点是否相同，可以有效避免解一中的特殊情况，且时间复杂度较低。