21. Merge Two Sorted Lists
給定兩個有序鏈表的頭節點 list1 和 list2。
將這兩個鏈表合併成一個有序鏈表。這個鏈表應該由前兩個鏈表的節點拼接而成。
返回合併後的鏈表的頭節點。
範例 1：
輸入：list1 = [1,2,4], list2 = [1,3,4] 輸出：[1,1,2,3,4,4]
Python
# 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: Optional[ListNode], list2: Optional[ListNode])
-> Optional[ListNode]:
# Create a dummy node to simplify edge cases
dummy = ListNode()
current = dummy
# Iterate while both lists are non-empty
while list1 and list2:
if list1.val <= list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
# Attach the remaining elements from list1 or list2
if list1:
current.next = list1
elif list2:
current.next = list2
# Return the merged list, which starts at dummy.next
return dummy.next
16.39MB, 42ms
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
// Create a dummy node to simplify edge cases
ListNode dummy;
ListNode* current = &dummy;
// Iterate while both lists are non-empty
while (list1 != nullptr && list2 != nullptr) {
if (list1->val <= list2->val) {
current->next = list1;
list1 = list1->next;
} else {
current->next = list2;
list2 = list2->next;
}
current = current->next;
}
// Attach the remaining elements from list1 or list2
if (list1 != nullptr) {
current->next = list1;
} else if (list2 != nullptr) {
current->next = list2;
}
// Return the merged list, which starts at dummy.next
return dummy.next;
}
};
18.23MB, 3ms
Javascript
/**
* 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) {
// Create a dummy node to simplify edge cases
let dummy = new ListNode();
let current = dummy;
// Iterate while both lists are non-empty
while (list1 !== null && list2 !== null) {
if (list1.val <= list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
current = current.next;
}
// Attach the remaining elements from list1 or list2
if (list1 !== null) {
current.next = list1;
} else if (list2 !== null) {
current.next = list2;
}
// Return the merged list, which starts at dummy.next
return dummy.next;
};
51.29MB, 61ms
