Leetcode 相交链表

• 使用python的三种解法
• • 自己解法
  • 哈希表方法
  • 快慢指针方法

使用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. 最终会在交点相遇。

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

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