題目描述

輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。

思路

依次遍歷兩個鏈表，比較兩個鏈表的元素，采用尾插法，小的先插入鏈表，大的后插入鏈表

代碼# -*- coding:utf-8 -*-

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# 返回合并后列表

def Merge(self, pHead1, pHead2):

# write code here

phNew = ListNode(0);

tmp = phNew

while pHead1 != None and pHead2 != None:

if pHead1.val > pHead2.val:

tmp.next = pHead2

pHead2 = pHead2.next

else:

tmp.next = pHead1

pHead1 = pHead1.next

tmp = tmp.next#注意將待插入鏈表頭后移

if (pHead1 != None):

tmp.next = pHead1

if (pHead2 != None):

tmp.next = pHead2

return phNew.next

注意

錯誤代碼：# -*- coding:utf-8 -*-

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None

class Solution:

# 返回合并后列表

def Merge(self, pHead1, pHead2):

# write code here

if pHead1 == None or pHead2 == None:#若其中一個為空，另一個不為空，也是可以滿足題意的。見代碼下方的測試用例

return

phNew = ListNode(0);

tmp = phNew

while pHead1 != None and pHead2 != None:

if pHead1.val > pHead2.val:

tmp.next = pHead2

pHead2 = pHead2.next

else:

tmp.next = pHead1

pHead1 = pHead1.next

tmp = tmp.next

if (pHead1 != None):

tmp.next = pHead1

if (pHead2 != None):

tmp.next = pHead2

return phNew.next

測試用例:

{1,3,5},{}

對應輸出應該為:

{1,3,5}

你的輸出為:

{}

總結

以上是生活随笔為你收集整理的链表 python 牛客_牛客网《剑指offer》之Python2.7实现：合并两个排序的链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。