題目描述

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

知識點

鏈表，歸并

Qiang的思路

顯然，這道題是一個歸并問題，與歸并排序中的歸并過程不同的是對鏈表進行歸并。但是可以采取相同的思路實現(xiàn)。

首先遍歷兩個鏈表，當有一個為空時停止遍歷，然后分別去遍歷兩個鏈表，最后完成歸并。

# -*- 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
        head=ListNode(None)
        result=head
        while pHead1!=None and pHead2!=None:
            if pHead1.val<pHead2.val:
                head.next=pHead1
                head=head.next
                pHead1=pHead1.next
            else:
                head.next=pHead2
                head=head.next
                pHead2=pHead2.next
        while pHead1!=None:
            head.next=pHead1
            head=head.next
            pHead1=pHead1.next
        while pHead2!=None:
            head.next=pHead2
            head=head.next
            pHead2=pHead2.next
        return result.next

作者原創(chuàng)，如需轉(zhuǎn)載及其他問題請郵箱聯(lián)系：lwqiang_chn@163.com。
個人網(wǎng)站：https://www.myqiang.top。