已知兩個已排序鏈表頭節點指針headA與headB，將這兩個鏈表合并，合并后仍為 有序的，返回合并后的頭節點。

主要步驟如下：

1. 創建一個臨時的頭節點，頭節點每次指向headA 或者 headB較小的節點
2. 當headA->data 比headB->data小的時候，headA的當前節點加入臨時頭節點，同時headA指針向后移動；否則headB加入臨時頭節點，同時headB指針向后移動
3. 當headA或者headB鏈表為空的時候，將另一個不為空的節點加入臨時頭節點。
   

算法實現如下：

Data *merge_list(Data *headA, Data *headB) {Data p;p.data = 0;p.next = NULL;Data *result = &p;/*構建臨時頭節點*/while (headA && headB) {if (headA->data < headB->data) {result->next = headA;headA = headA->next;} else {result->next = headB;headB = headB ->next;} result = result -> next;}if (headA == NULL) {result ->next = headB;} if (headB == NULL) {result ->next = headA;}return p.next;
}

遞歸方式更優實現如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {if(l1 == NULL) {return l2;}if (l2 == NULL) {return l1;}ListNode *head = l1 -> val < l2 -> val ?l1:l2; //取一個鏈表節點ListNode *nohead = l1->val < l2 -> val ?l2:l1;//保證另一個鏈表節點無變化head->next = mergeTwoLists(head -> next, nohead);return head;}
};

源碼測試如下：

#include <stdio.h>
#include <stdlib.h>typedef struct Link_list
{/* data */int data;struct Link_list *next;
}Data;/*打印鏈表*/
void print_list(Data *head) {while (head) {printf("%d ",head->data);head = head -> next;}printf("\n");
}
/*尾插法構造鏈表*/
Data *insert_tail(Data *head, int n) {head = (Data *)malloc(sizeof(Data));head->next = NULL;Data *r = head;int b;while(n--){scanf("%d",&b);Data *p = (Data *)malloc(sizeof(Data));p->data = b;r->next = p;p->next = NULL;r = p;}return head;
}
/*合并有序鏈表*/
Data *merge_list(Data *headA, Data *headB) {Data p;p.data = 0;p.next = NULL;Data *result = &p;while (headA && headB) {if (headA->data < headB->data) {result->next = headA;headA = headA->next;} else {result->next = headB;headB = headB ->next;} result = result -> next;}if (headA == NULL) {result ->next = headB;} if (headB == NULL) {result ->next = headA;}return p.next;
}int main(){Data *headA,*headB;printf("construct first list : \n");//尾插法構造一個五節點的鏈表headA = insert_tail(headA,5);printf("construct second list :\n");//尾插法構造一個三節點的鏈表headB = insert_tail(headB,3);Data *result = merge_list(headA->next,headB->next);printf("merge the list :\n");print_list(result);return 0;
}

輸出如下：

construct first list : 
1 4 5 6 7
construct second list :
5 6 7
merge the list :
1 4 5 5 6 6 7 7

總結

以上是生活随笔為你收集整理的C语言的有序单链表合并的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。