Leetcode160 相交链表

题目描述

file
file

解法1:

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

class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p, q = headA, headB
while(p != q):
p = p.next if p else headB
q = q.next if q else headA
return p


 

解法2:

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

class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
visited = set()
while headA:
visited.add(headA)
headA = headA.next
while headB:
if headB in visited:
return headB
headB = headB.next
return None


 

Note

  • 解法1是通过“增加”来消除长度差
    file
  • 解法2是通过字典实现,效率更高。