【数组 &双指针】Leecode-160. 相交链表

【题目】

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

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

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

【题解】

题解1：

• 思路

          遍历两个链表将节点加入到列表中，然后从尾部遍历列表

• 复杂度

         时间复杂度：O(n)，空间复杂度：O(n)

• 代码

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        NodeA,NodeB = headA, headB
        S1,S2 = [], []
        while NodeA:
            S1.append(NodeA)
            NodeA = NodeA.next
        while NodeB:
            S2.append(NodeB)
            NodeB = NodeB.next
        ans = None
        i, j = len(S1) - 1, len(S2) - 1
        while i >= 0 and j >= 0 and S1[i] == S2[j]:
            ans = S1[i]
            i, j = i - 1, j - 1
        return ans

题解2：

• 思路

       遍历链表，当遍历到尾部指针重置为另一个链表的头结点，如果两个链表相交那么必然在相交点相遇

• 复杂度

         时间复杂度：O(m+n)，空间复杂度：O(1)

• 代码

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

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        NodeA,NodeB = headA, headB
        while NodeA != NodeB:
            NodeA = NodeA.next if NodeA else headB
            NodeB = NodeB.next if NodeB else headA
        return NodeA