首页 > 代码库 > Leetcode 160. Intersection of two linked lists

Leetcode 160. Intersection of two linked lists

2024-08-26 22:05:34   220人阅读

Write a program to find the node at which the intersection of two singly linked lists begins.

 

For example, the following two linked lists: 

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

 

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.
 1 class Solution(object):
 2     def getIntersectionNode(self, headA, headB):
 3         """
 4         :type head1, head1: ListNode
 5         :rtype: ListNode
 6         """
 7         
 8         n = self.getLength(headA)
 9         m = self.getLength(headB)
10         
11         if n < m:
12             return self.getIntersectionNode(headB, headA)
13         
14         for i in range(n-m):
15             headA = headA.next
16         
17         while headA and headB:
18             if id(headA) == id(headB):
19                 return headA
20             headA = headA.next
21             headB = headB.next
22         return None
23     
24     def getLength(self, head):
25         n = 0
26         while head:
27             head = head.next
28             n += 1
29         return n
 
1. 总是先操作长度较短的那个list. 
2. 用id(headA) == id(headB) 判断两个node是不是一样

Leetcode 160. Intersection of two linked lists


联系
我们