Leetcode 160.相交链表

Leetcode 相交链表

使用python的三种解法

自己解法

拿到题之后,可以想到长链表比短链表要先多走差值步,两者才能同时到达相交点:

  1. 自定义链表长度函数
  2. 求链表长度差值
  3. 让较长的链表先行
  4. 返回交点
class Solution(object):
    def length(self,head):
        cur=head
        l=0
        while cur:
            l+=1
            cur=cur.next
        return l
    
    def getIntersectionNode(self, headA, headB):
        l1=self.length(headA)
        l2=self.length(headB)
        l=headA
        r=headB
        for _ in range(abs(l1-l2)):
            if l1>l2:
                l=l.next
            else:
                r=r.next
        while l:
            if l==r:
                return l
            else:
                l=l.next
                r=r.next
        return None

哈希表方法

  1. 使用哈希表记录一个链表中的结点
  2. 遍历下一个链表的结点
  3. 如果该结点在表中出现过返回结点
  4. 否则,继续迭代
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        hash_set=set()
        cur=headA
        while cur:
            hash_set.add(cur)
            cur=cur.next
        
        curr=headB
        while curr:
            if curr in hash_set:
                return curr
            curr=curr.next
        return None

快慢指针方法

  1. 给不同的链表一个指针
  2. 较短的链表首先到达终点
  3. 将到达终点的指针换到另一个链表的头节点
  4. 最终会在交点相遇

[如图,图片来源于网络,侵删。]

Leetcode 160.相交链表

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        f=headA; s=headB
        while f != s:
            f=f.next if f else headB
            s=s.next if s else headA
        return f
上一篇:深圳高层次人才补助C


下一篇:160. 相交链表