LeetCode 160 相交連結串列

2022-09-22 06:41:43 字數 2508 閱讀 4914

問題描述:

編寫一個程式,找到兩個單連結串列相交的起始節點。

例如,下面的兩個連結串列

a:          a1 → a2

↘c1 → c2 → c3

b: b1 → b2 → b3

在節點 c1 開始相交。

方法1:

1

class

solution(object):

2def

getintersectionnode(self, heada, headb):

3"""

4:type head1, head1: listnode

5:rtype: listnode

6"""7if

not heada or

notheadb:

8return

none

9 p =heada

10 q =headb

11while p and

q:12

if p.val ==q.val:

1314

returnp15

elif p.val 16 p =p.next

17else

:18 q =q.next

19return none

官方:求出兩個表的長度,表長的先走一個差值。

1

class

solution(object):

2def

getintersectionnode(self, heada, headb):

3"""

4:type head1, head1: listnode

5:rtype: listnode

6"""

7 lena =0

8 heada_c1 =heada

9while

heada_c1:

10 lena += 1

11 heada_c1 =heada_c1.next

12 lenb =0

13 headb_c1 =headb

14while

headb_c1:

15 lenb += 1

16 headb_c1 =headb_c1.next

17 heada_c2 =heada

18 headb_c2 =headb

19if lena >lenb:

20for i in range(lena-lenb):

21 heada_c2 =heada_c2.next

22elif lena 23for i in range(lenb-lena):

24 headb_c2 =headb_c2.next

25while heada_c2 and

headb_c2:

26if heada_c2 ==headb_c2:

27return

heada_c2

28 headb_c2 =headb_c2.next

29 heada_c2 =heada_c2.next

30return none

方法3:

1

class

solution(object):

2def

getintersectionnode(self, heada, headb):

3"""

4:type head1, head1: listnode

5:rtype: listnode

6"""

7 temp =set()

8 tempa =heada

9 tempb =headb

1011

if heada and headb is

none:

12return

none

1314

while

tempa:

15temp.add(tempa)

16 tempa =tempa.next

1718

while

tempb:

19if tempb in

temp:

20return

tempb

21 tempb =tempb.next

2223

return none

2018-09-14 16:26:48

leetcode 160 相交連結串列

編寫一個程式,找到兩個單連結串列相交的起始節點。 如下面的兩個連結串列 在節點 c1 開始相交。 剛開始想到的是暴力解法,雙層迴圈遍歷兩個連...

LeetCode 160 相交連結串列

difficulty 簡單 編寫一個程式,找到兩個單連結串列相交的起始節點。 如下面的兩個連結串列 在節點 c1 開始相交。 示例 1 輸入...

LeetCode160 相交連結串列

編寫一個程式,找到兩個單連結串列相交的起始節點。 如下面的兩個連結串列 在節點 c1 開始相交。 示例 1 輸入 intersectval 8 lista 4 1 8 4 5 listb 5 0 1 8 4 5 skipa 2 skipb 3 輸出 reference of the node with va...