合并兩個有序鏈表的方法是使用雙指針來比較兩個鏈表的節點值,然后按照順序將節點連接起來。
具體步驟如下:
代碼示例:
#include <stdio.h>
#include <stdlib.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* p = newHead;
struct ListNode* p1 = l1;
struct ListNode* p2 = l2;
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) {
p->next = p1;
}
if (p2) {
p->next = p2;
}
return newHead->next;
}
int main() {
// 創建鏈表1: 1 -> 2 -> 4
struct ListNode* l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->val = 1;
l1->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->next->val = 2;
l1->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l1->next->next->val = 4;
l1->next->next->next = NULL;
// 創建鏈表2: 1 -> 3 -> 4
struct ListNode* l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->val = 1;
l2->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->next->val = 3;
l2->next->next = (struct ListNode*)malloc(sizeof(struct ListNode));
l2->next->next->val = 4;
l2->next->next->next = NULL;
// 合并兩個有序鏈表
struct ListNode* mergedList = mergeTwoLists(l1, l2);
// 輸出合并后的鏈表:1 -> 1 -> 2 -> 3 -> 4 -> 4
while (mergedList) {
printf("%d ", mergedList->val);
mergedList = mergedList->next;
}
return 0;
}
輸出結果: 1 1 2 3 4 4