leetcode21：合并两个有序链表

题目链接

leetcode

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。

C++ 代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <vector>
using namespace std;

// 链表结点的定义
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) {}
};

// 辅助函数：创建链表
ListNode* createList(const vector<int>& nums) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int num : nums) {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    return dummy->next;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val;
        if (head->next != nullptr) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head) {
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

/*
    递归实现
    
    时间复杂度：O(m+n)
        其中 m 和 n 分别是两个链表的长度，遍历两个链表各一次。
    空间复杂度：O(m+n)
        递归调用函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。
        结束递归调用时，函数最多调用 m+n，所以空间复杂度为 O(m+n)。
*/
class Solution_0 {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p1 = list1, *p2 = list2;
        if (!p1) return p2;
        if (!p2) return p1;

        if (p1->val < p2->val) {
            p1->next = mergeTwoLists(p1->next, p2);
            return p1;
        } else {
            p2->next = mergeTwoLists(p1, p2->next);
            return p2;
        }
    }
};

/*
    迭代实现

    虚拟头结点，dummy 节点相当于是占位符，可以避免处理空指针的情况。
    l1, l2 类似于拉链两侧的锯齿，指针 p 是拉链的拉索，将两个有序链表合并。

    时间复杂度：O(n)
        其中 n 和 m 分别为两个链表的长度，遍历两个链表各一次。
    空间复杂度：O(1)
        只使用了固定的几个额外节点，不随输入规模增长而增长。
*/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new ListNode(-1), *p = dummy;
        ListNode *p1 = list1, *p2 = list2;

        while (p1 && p2) {
            if (p1->val < p2->val) {
                p->next = p1;
                p1 = p1->next;
            } else {
                p->next = p2;
                p2 = p2->next;
            }
            p = p->next;
        }
        // if (p1) {
        //     cur->next = p1;
        // }
        // if (p2) {
        //     cur->next = p2;
        // }
        p->next = (p1 ? p1 : p2);
        return dummy->next;
    }
};

int main() {
    // 示例输入
    Solution solution;
    vector<int> l1_nums = {1, 2, 4};
    vector<int> l2_nums = {1, 3, 4};

    // 创建链表
    ListNode* l1 = createList(l1_nums);
    ListNode* l2 = createList(l2_nums);

    // 合并操作
    ListNode* result = solution.mergeTwoLists(l1, l2);
    // 打印结果
    cout << "Result: ";
    printList(result);

    // 释放内存
    deleteList(l1);
    deleteList(l2);
    deleteList(result);

    return 0;
}

Golang 代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
package main

import "fmt"

// 定义链表节点
type ListNode struct {
    Val  int
    Next *ListNode
}

// createLinkedList 创建链表
func createLinkedList(values []int) *ListNode {
	if len(values) == 0 {
		return nil
	}
	head := &ListNode{Val: values[0]}
	current := head
	for _, val := range values[1:] {
		current.Next = &ListNode{Val: val}
		current = current.Next
	}
	return head
}

// printLinkedList 打印链表
func printLinkedList(head *ListNode) string {
	var result []int
	for head != nil {
		result = append(result, head.Val)
		head = head.Next
	}
	return fmt.Sprintf("%v", result)
}

/*
    递归实现

    如果 l1 或 l2 为空，则返回不为空的链表。
    如果 l1 的值小于 l2 的值，则将 l1 的下一个节点和 l2 合并，并返回合并后的链表。
    如果 l2 的值小于 l1 的值，则将 l2 的下一个节点和 l1 合并，并返回合并后的链表。   
    重复上述步骤，直到两个链表都为空。
    返回合并后的链表。
    
    时间复杂度：O(m+n)
        其中 m 和 n 分别是两个链表的长度，遍历两个链表各一次。
    空间复杂度：O(m+n)
        递归调用栈的深度为 m+n，所以空间复杂度为 O(m+n)。
*/
func mergeTwoLists_0(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    if l1.Val < l2.Val {
        l1.Next = mergeTwoLists_0(l1.Next, l2)
        return l1
    } else {
        l2.Next = mergeTwoLists_0(l1, l2.Next)
        return l2
    }
}

/*
    迭代实现

    创建一个 dummy 节点，指向头部。
    两个指针分别指向两个链表的头部。
    比较两个指针指向节点的值，将较小的节点添加到 dummy 节点后面，直到两个指针指向的节点都为空。
    将剩余的节点添加到 dummy 节点的后面。
    返回合并后链表的头部。

    时间复杂度：O(m+n)
        其中 m 和 n 分别是两个链表的长度，遍历两个链表各一次。
    空间复杂度：O(1)
        只使用了固定的几个额外节点，不随输入规模增长而增长。
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{Val: -1, Next: nil}
    cur := dummy

    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }
    return dummy.Next
}

func main() {
    // 测试用例
    testCases := []struct {
        l1      []int
        l2      []int
        expected []int
    }{
        {
            l1:       []int{1,2,4},
            l2:       []int{1,3,4},
            expected: []int{1,1,2,3,4,4},
        },
        {
            l1:       []int{},
            l2:       []int{},
            expected: []int{},
        },
        {
            l1:       []int{},
            l2:       []int{0},
            expected: []int{0},
        },
    }

    for i, tc := range testCases {
		head1 := createLinkedList(tc.l1)
		head2 := createLinkedList(tc.l2)
        fmt.Printf("Test Case %d, Input: l1 = %v, l2 = %v\n", i+1, printLinkedList(head1), printLinkedList(head2))
		result := mergeTwoLists(head1, head2)
		resultStr := printLinkedList(result)
        expectedStr := fmt.Sprintf("%v", tc.expected)
        
        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
	}
}
#leetcode
leetcode21：合并两个有序链表
https://lcf163.github.io/2023/09/26/leetcode21：合并两个有序链表/
作者
乘风的小站
发布于
2023年9月26日
许可协议