LeetCode 021 合併兩個有序連結串列

2022-09-22 06:51:54 字數 1430 閱讀 3999

問題描述:

將兩個有序連結串列合併為一個新的有序連結串列並返回。新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。 

示例:

輸入:1->2->4, 1->3->4輸出:1->1->2->3->4->4

方法1:

1

class

solution(object):

2def

mergetwolists(self, l1, l2):

3"""

4:type l1: listnode

5:type l2: listnode

6:rtype: listnode

7"""

8 p = dummy = listnode(-1)

9while l1 and

l2:10

if l1.val <=l2.val:

11 p.next =listnode(l1.val)

12 l1 =l1.next

13else

:14 p.next =listnode(l2.val)

15 l2 =l2.next

16 p =p.next

17 p.next = l1 or

l218

return dummy.next

方法2:遞迴

1

class

solution(object):

2def

mergetwolists(self, l1, l2):

3"""

4:type l1: listnode

5:type l2: listnode

6:rtype: listnode

7"""

8if l1 ==none:

9return

l210

if l2 ==none:

11return

l112 mergel = none #

設定新連結串列

13if l1.val 14 mergel =l1

15 mergel.next =self.mergetwolists(l1.next, l2)

16else

:17 mergel =l2

18 mergel.next =self.mergetwolists(l1, l2.next)

19return

mergel

20