leetcode
January 10, 2024

Viiisit [LeetCode] - 21. Merge Two Sorted Lists

#php#javascript#ruby

keep learning, keep coding!

Problem - Merge Two Sorted Lists

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

Merge the two lists into 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.

翻譯蒟蒻

將兩個已排序的鏈表整合成一個新的已排序鏈表，並返回新鏈表的 head。

Solution - JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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) {
    // 建立一個虛擬的節點 dummy 
    let dummy = new ListNode(0);
    
    // 指針 curr 指向 dummy 節點，用於遍歷和構建新的鏈表。
    let curr = dummy;
    
    // 當 list1 和 list2 都不為 null 時，進入循環。
    while (list1 && list2) {
        // 如果 list1 的當前節點的值小於 list2 的當前節點的值，則將 curr 的 next 指向 list1 的當前節點。
        if (list1.val < list2.val) { 
            curr.next = list1; 
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    
    curr.next = list1 || list2; // 如果 list1 或 list2 中有一個還有剩餘的節點，則將 curr 的 next 指向該鏈表的剩餘部分。
    
    // 返回合併後的鏈表。由於 dummy 節點是為了操作而建的，所以返回 dummy 的下一個節點，就是合併後的鏈表的 head。
    return dummy.next;
};

Solution - Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge_two_lists(list1, list2)
  dummy_head = ListNode.new
  current = dummy_head

  while list1 && list2
    if list1.val < list2.val
      current.next = list1
      list1 = list1.next
    else
      current.next = list2
      list2 = list2.next
    end
    current = current.next
  end

  current.next = list1 || list2

  dummy_head.next
end

Solution - PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function mergeTwoLists($list1, $list2) {
  $dummy = new ListNode(0);
  $cur = $dummy;
  while ($list1 && $list2) {
    if ($list1->val < $list2->val) {
      $cur->next = $list1;
      $list1 = $list1->next;
    } else {
      $cur->next = $list2;
      $list2 = $list2->next;
    }
    $cur = $cur->next;
  }
  $cur->next = $list1 ? $list1 : $list2;
  return $dummy->next;
}

LeetCode 傳送門 - Merge Two Sorted Lists