21. Merge Two Sorted Lists
Tags:
Easy
Skills:
Linked List
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach - Iterative
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
14 const dummy = new ListNode(0);
15 let curr = dummy;
16
17 while(list1 !== null && list2 !== null) {
18 if(list1.val <= list2.val) {
19 curr.next = list1;
20 list1 = list1.next;
21 } else {
22 curr.next = list2;
23 list2 = list2.next;
24 }
25 curr = curr.next;
26 }
27
28 curr.next = list1 !== null ? list1 : list2;
29 return dummy.next;
30};Approach - Recursive
1/**
2 * Definition for singly-linked list.
3 * class ListNode {
4 * val: number
5 * next: ListNode | null
6 * constructor(val?: number, next?: ListNode | null) {
7 * this.val = (val===undefined ? 0 : val)
8 * this.next = (next===undefined ? null : next)
9 * }
10 * }
11 */
12
13function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
14 if(list1 === null) return list2;
15 if(list2 === null) return list1;
16
17 if(list1.val <= list2.val) {
18 list1.next = mergeTwoLists(list1.next, list2);
19 return list1;
20 } else {
21 list2.next = mergeTwoLists(list1, list2.next);
22 return list2;
23 }
24};| Tiêu chí | Iterative (Lặp lại) | Recursive (Đệ quy) |
| Cách tiếp cận | Dùng vòng lặp (while), hai con trỏ duyệt song song hai danh sách. | Hàm tự gọi lại chính nó cho đến khi một danh sách hết (base case). |
| Độ dài code | Thường dài hơn một chút do cần quản lý con trỏ và dummy node. | Code ngắn gọn, súc tích hơn. |
| Độ phức tạp thời gian | O(m+n) với m, n là số node của hai danh sách. | O(m+n), giống iterative. |
| Độ phức tạp bộ nhớ | O(1), không dùng thêm stack ngoài các biến con trỏ. | O(m+n) do mỗi lần gọi hàm đệ quy sẽ chiếm thêm stack frame. |
| Dễ hiểu | Dễ hình dung, phù hợp cho người mới học linked list. | Dễ viết hơn, nhưng có thể khó hiểu với người chưa quen đệ quy. |
| Khả năng mở rộng | Không bị giới hạn bởi stack, dùng tốt cho danh sách rất dài. | Có thể gây stack overflow nếu danh sách quá dài (vượt quá giới hạn call stack). |
| Tái sử dụng node | Có, không tạo node mới, chỉ thay đổi con trỏ. | Có, không tạo node mới, chỉ thay đổi con trỏ. |