[剑指offer]52.两个链表的第一个公共节点

52.两个链表的第一个公共节点

方法一：双堆栈

思路：分别建立两个空堆栈stackA和stackB，headA、headB的节点分别依次存放入两个堆栈中。采用堆栈后进先出的性质，从后往前对比元素，并赋值给res，直到遇上不同元素，或者其中一个栈空了为止。

代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
       
        stackA = []
        stackB = []
        while headA:
            stackA.append(headA)
            headA = headA.next
        while headB:
            stackB.append(headB)
            headB = headB.next
        res = None
        while stackA and stackB:
            nodeA = stackA.pop()
            nodeB = stackB.pop()
            if nodeA == nodeB:
                res = nodeA
                if not stackA or not stackB:
                    return res
            else:
                return res

结果

执行用时 :176 ms, 在所有 Python3 提交中击败了77.36%的用户
内存消耗 :28.7 MB, 在所有 Python3 提交中击败了100.00%的用户

方法二 双指针

思路：先求出两个链表的长度lenA和lenB，再让长的链表先走长度差的步数。开始遍历列表，若不满足headA ！= headB，跳出while循环，返回当前节点值；若链表已经被遍历完，说明两个链表中不存在相同值，返回None。

代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        lenA = 0
        lenB = 0
        tempA = headA
        tempB = headB
        while headA:
            lenA += 1
            headA = headA.next
        while headB:
            lenB += 1
            headB = headB.next
        headA = tempA
        headB = tempB
        if lenA < lenB:
            for i in range(lenB - lenA):
                headB = headB.next  
            while headA != headB and headA:
                headA = headA.next
                headB = headB.next
            
        else:
            for i in range(lenA - lenB):
                headA = headA.next
            while headA != headB and headA:
                headA = headA.next
                headB = headB.next

        if not headA:
            return None
        else:
            return headA

结果

执行用时 :304 ms, 在所有 Python3 提交中击败了7.12%>的用户
内存消耗 :28.6 MB, 在所有 Python3 提交中击败了100.00%的用户