leetcode面试题 02.07. 链表相交

题目

思路

• 方案一：使用哈希表储存一个链表节点，在另一个链表进行查询是否有相同节点
• 方案二：统计两个链表长度，然后末尾对齐，判断是否有相同节点

代码

使用哈希表set

# 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) -> ListNode:
        cur_a = headA
        cur_b = headB
        set_a = set()
        while cur_a:
            if cur_a not in set_a:  # 建立哈希表set
                set_a.add(cur_a)
            cur_a = cur_a.next
        while cur_b:
            if cur_b in set_a:  # 查询哈希表set
                return cur_b
            cur_b = cur_b.next
        return None

统计长度末尾对齐

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA, lenB = 0, 0
        cur = headA
        while cur:         # 求链表A的长度
            cur = cur.next 
            lenA += 1
        cur = headB 
        while cur:         # 求链表B的长度
            cur = cur.next 
            lenB += 1
        curA, curB = headA, headB
        if lenA > lenB:     # 让curB为最长链表的头，lenB为其长度
            curA, curB = curB, curA
            lenA, lenB = lenB, lenA 
        for _ in range(lenB - lenA):  # 让curA和curB在同一起点上（末尾位置对齐）
            curB = curB.next 
        while curA:         #  遍历curA 和 curB，遇到相同则直接返回
            if curA == curB:
                return curA
            else:
                curA = curA.next 
                curB = curB.next
        return None