劍指 Offer 25. 合并兩個(gè)排序的鏈表

輸入兩個(gè)遞增排序的鏈表，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。

示例1：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

我真是傻了，我居然一開始想p對應(yīng)l1，然后q對應(yīng)l2,然后一個(gè)一個(gè)比插l1里面去，結(jié)果就是特別特別麻煩。

直接應(yīng)該就是開個(gè)新的鏈表，然后l1,l2一個(gè)一個(gè)比過去，就很簡單了。

#?Definition?for?singly-linked?list.

#?class?ListNode:

#?????def?__init__(self,?x):

#?????????self.val?=?x

#?????????self.next?=?None

class?Solution:

????def?mergeTwoLists(self,?l1:?ListNode,?l2:?ListNode)?->?ListNode:

????????p=ListNode(0)

????????q=p

????????while?l1?and?l2:

????????????if?l1.val<l2.val:

????????????????p.next=l1

????????????????l1=l1.next

????????????????p=p.next

????????????else:

????????????????p.next=l2

????????????????l2=l2.next

????????????????p=p.next

????????if?l1:?p.next=l1

????????else:

????????????p.next=l2

????????return?q.next

在一開始就設(shè)置q記錄p所在鏈表的頭結(jié)點(diǎn)，最后返回就會很簡單。