合并兩個已排序的鏈表

ormsf 發(fā)布于2019-07-25 12:04 / 3305人閱讀

摘要：合并兩個已排序的鏈表合并兩個已排序的鏈表，新鏈表中的每個節(jié)點必須是來自輸入的兩個鏈表的節(jié)點即不能構(gòu)造新的節(jié)點，返回新鏈表的頭部。

合并兩個已排序的鏈表 Merge Two Sorted Lists

合并兩個已排序的鏈表，新鏈表中的每個節(jié)點必須是來自輸入的兩個鏈表的節(jié)點（即不能構(gòu)造新的節(jié)點），返回新鏈表的頭部。

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

example 1

input: 1->2->4, 3->8
output: 1->2->3->4->8

思路

head指向輸入兩個鏈表中頭節(jié)點較小值，作為新鏈表的頭部

tail指向新鏈表表尾，初始狀態(tài)head = tail

a掃描l1，b掃描l2，比較a和b節(jié)點內(nèi)值的大小，將較小的加入tail之后，a和b中較小的向后移動一個節(jié)點，較大的不動，tail向后移動一個節(jié)點保證任意時候指向都是新鏈表尾部

l1和l2其中一個已經(jīng)遍歷完，若另一個還有元素，添加到tail之后

代碼

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if None in (l1, l2):
            return l1 or l2
        head = tail = l1 if l1.val <= l2.val else l2
        a = l1 if l1.val > l2.val else l1.next
        b = l2 if l1.val <= l2.val else l2.next
        while a and b:
            if a.val <= b.val:
                tail.next = a
                tail, a = tail.next, a.next
            else:
                tail.next = b
                tail, b = tail.next, b.next
        tail.next = a or b
        return head

本題以及其它leetcode題目代碼github地址: github地址