Not a programmer 不工程的攻城獅

LeetCode Solution, Easy, 21. Merge Two Sorted Lists

合併兩個排序序列

攻城獅's photo
攻城獅

21. Merge Two Sorted Lists

題目敘述

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

merge_ex1.jpeg

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

  • The number of nodes in both lists is in the range [0, 50].
  • -100 <= Node.val <= 100
  • Both list1 and list2 are sorted in non-decreasing order.

題目翻譯

有兩個排序序列 list1 和 list2，要將其合併成一個序列並且要是排序的。

解法解析

解法上就是依舊使用 Iteration 和 Recursion 的方式來處理，使用上 Iteration 的方式可以有更好的空間複雜度。

解法範例

Go

Recursion
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }
    if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    }
    list2.Next = mergeTwoLists(list1, list2.Next)
    return list2
}
Iteration
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    var prehead ListNode = ListNode{}

    var prev *ListNode = &prehead
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            prev.Next = list1
            list1 = list1.Next
        } else {
            prev.Next = list2
            list2 = list2.Next
        }
        prev = prev.Next
    }
    if list1 != nil {
        prev.Next = list1
    } else {
        prev.Next = list2
    }
    return prehead.Next
}

JavaScript

Recursion
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    if (list1 === null) {
        return list2;
    }
    if (list2 === null) {
        return list1;
    }
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
};
Iteration
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
    let prehead = new ListNode(0);

    let prev = prehead;
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            prev.next = list1;
            list1 = list1.next;
        } else {
            prev.next = list2;
            list2 = list2.next;
        }
        prev = prev.next;
    }

    prev.next = list1 || list2;
    return prehead.next;
};

Kotlin

Recursion
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        return when {
            list1 == null -> list2
            list2 == null -> list1
            list1.`val` < list2.`val` -> {
                list1.next = mergeTwoLists(list1.next, list2)
                list1
            }
            else -> {
                list2.next = mergeTwoLists(list1, list2.next)
                list2
            }
        }
    }
}
Iteration
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        var prehead: ListNode? = ListNode(0)

        var prev: ListNode? = prehead
        var l1: ListNode? = list1
        var l2: ListNode? = list2
        while (l1 != null && l2 != null) {
            if (l1.`val` <= l2.`val`) {
                prev?.next = l1
                l1 = l1.next
            } else {
                prev?.next = l2
                l2 = l2.next
            }
            prev = prev?.next
        }
        prev?.next = if (l1 != null) l1 else l2
        return prehead?.next
    }
}

PHP

Recursion
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2)
    {
        if (is_null($list1)) {
            return $list2;
        }
        if (is_null($list2)) {
            return $list1;
        }
        if ($list1->val <= $list2->val) {
            $list1->next = $this->mergeTwoLists($list1->next, $list2);
            return $list1;
        }
        $list2->next = $this->mergeTwoLists($list1, $list2->next);
        return $list2;
    }
}
Iteration
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $list1
     * @param ListNode $list2
     * @return ListNode
     */
    function mergeTwoLists($list1, $list2)
    {
        $prehead = new ListNode(0);

        $prev = $prehead;
        while (!is_null($list1) && !is_null($list2)) {
            if ($list1->val <= $list2->val) {
                $prev->next = $list1;
                $list1 = $list1->next;
            } else {
                $prev->next = $list2;
                $list2 = $list2->next;
            }
            $prev = $prev->next;
        }
        $prev->next = $list1 ?? $list2;
        return $prehead->next;
    }
}

Python

Recursion
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: ListNode | None, list2: ListNode | None
    ) -> ListNode | None:
        if list1 is None:
            return list2
        if list2 is None:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2
Iteration
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(
        self, list1: ListNode | None, list2: ListNode | None
    ) -> ListNode | None:
        # maintain an unchanging reference to node ahead of the return node.
        prehead = ListNode(-1)

        prev = prehead
        while list1 and list2:
            if list1.val <= list2.val:
                prev.next = list1
                list1 = list1.next
            else:
                prev.next = list2
                list2 = list2.next
            prev = prev.next

        # At least one of list1 and list2 can still have nodes at this point, so connect
        # the non-null list to the end of the merged list.
        prev.next = list1 or list2

        return prehead.next

Rust

Swift

Recursion
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        guard list1 != nil else {
            return list2
        }
        guard list2 != nil else {
            return list1
        }

        var result: ListNode? = nil
        if list1!.val < list2!.val {
            result = list1
            result!.next = mergeTwoLists(list1!.next, list2)
        } else {
            result = list2
            result!.next = mergeTwoLists(list1, list2!.next)
        }
        return result
    }
}
Iteration
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        var prehead: ListNode? = ListNode(0)

        var prev: ListNode? = prehead
        var l1: ListNode? = list1
        var l2: ListNode? = list2
        while l1 != nil && l2 != nil {
            if l1!.val <= l2!.val {
                prev?.next = l1
                l1 = l1?.next
            } else {
                prev?.next = l2
                l2 = l2?.next
            }

            prev = prev?.next
        }

        prev?.next = (l1 == nil) ? l2 : l1
        return prehead?.next
    }
}

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

leetcodelearn codingGeneral ProgrammingProgramming Blogscoding