题目简述:
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.
解题思路:
首先这道题目有他的特殊性,这个特殊性就在这里的两个链表如果有交集的话,那么他们在最后面的一定都是相同的。
所以这里催生了两种想法:
从后往前比较,找到最后形同的那个
-
从前往后比较,但是这里要用到一个技巧。我们首先要去获取到这两个链表的长度,然后让长度长的那个先多走长度差的距离,最后再开始比较,第一个相同的即是。
这里使用了第二种思路:Definition for singly-linked list.
class ListNode:
def init(self, x):
self.val = x
self.next = Noneclass Solution:
@param two ListNodes
@return the intersected ListNode
def getIntersectionNode(self, headA, headB):
ta = ListNode(0)
tb = ListNode(0)
ta = headA
tb = headB
la = 0
lb = 0
while ta != None:
la += 1
ta = ta.next
while tb != None:
lb += 1
tb = tb.next
if la > lb :
ta = headA
tb = headB
tt = la - lb
while tt > 0:
ta = ta.next
tt -= 1
while ta != None and tb != None:
if ta == tb:
return ta
ta = ta.next
tb = tb.next
return Noneelse:
ta = headA
tb = headB
tt = lb -la
while tt > 0:
tb = tb.next
tt -= 1
while ta != None and tb != None:
if ta.val == tb.val:
return ta
ta = ta.next
tb = tb.next
return None