-
Notifications
You must be signed in to change notification settings - Fork 0
/
21.合并两个有序链表.cpp
157 lines (153 loc) · 4.3 KB
/
21.合并两个有序链表.cpp
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/*
* @lc app=leetcode.cn id=21 lang=cpp
*
* [21] 合并两个有序链表
*
* https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
*
* algorithms
* Easy (60.46%)
* Likes: 905
* Dislikes: 0
* Total Accepted: 211.3K
* Total Submissions: 349.1K
* Testcase Example: '[1,2,4]\n[1,3,4]'
*
* 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
*
* 示例：
*
* 输入：1->2->4, 1->3->4
* 输出：1->1->2->3->4->4
*
*
*/
// @lc code=start
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
//
// ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// if(!l1 && l2){
// return l2;
// }
// else if(l1 && !l2){
// return l1;
// }
// auto ret = new ListNode(0);
// auto retBuf = ret;
// while (l2) {
// retBuf->next = new ListNode(l2->val);
// retBuf = retBuf->next;
// l2 = l2->next;
// }
// retBuf = ret->next;
// auto loc = ret;
// while (l1 || l2) {
// auto x1 = l1->val;
// auto flag = 1;
// while (retBuf) {
// auto x2 = retBuf->val;
// if (x1 == x2) {
// loc = retBuf;
// flag = 0;
// //retBuf = retBuf->next;
// break;
// }
// else if (x1 < x2) {
// loc = retBuf;
// flag = -1;
// //retBuf = retBuf->next;
// break;
// }
// flag = 1;
// loc = retBuf;
// retBuf = retBuf->next;
// }
// switch (flag) {
// case 0: {
// auto tmp = loc->next;
// loc->next = new ListNode(x1);
// loc->next->next = tmp;
// loc = loc->next;
// }
// break;
// case -1: {
// auto tmp = loc->next;
// loc->next = new ListNode(x1);
// loc->next->next = tmp;
// int num = 0;
// num = loc->val;
// loc->val = loc->next->val;
// loc->next->val = num;
// loc = loc->next;
// }
// break;
// default: {
// loc->next = new ListNode(x1);
// loc = loc->next;
// }
// break;
// }
// l1 = l1->next;
// }
// return ret->next;
// }
// 递归，会修改原始数据，这样做是否合理，我表示疑惑
// ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
// if(!l1){
// return l2;
// }
// else if(!l2){
// return l1;
// }
// else if(l1->val < l2->val){
// l1->next = mergeTwoLists(l1->next, l2);
// return l1;
// }
// else{
// l2->next = mergeTwoLists(l1, l2->next);
// return l2;
// }
// }
// 迭代，不会修改原始数据，迭代的方法只是返回一个重新的组织的链表头指针
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
auto ret = new ListNode(0);
auto prev = ret;
while (l1 || l2) {
if (l1 && l2) {
auto x1 = l1->val;
auto x2 = l2->val;
if (x1 < x2) {
prev->next = l1;
prev = prev->next;
l1 = l1->next;
}
else {
prev->next = l2;
prev = prev->next;
l2 = l2->next;
}
}
else if (!l1) {
prev->next = l2;
prev = prev->next;
l2 = l2->next;
}
else {
prev->next = l1;
prev = prev->next;
l1 = l1->next;
}
}
return ret->next;
}
};
// @lc code=end