C語言如何合并兩個帶頭節點升序排列鏈表

這篇文章將為大家詳細講解有關C語言如何合并兩個帶頭節點升序排列鏈表，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

合并鏈表，顧名思義，就是將兩個按順序存放數據的鏈表中的數據合并為用一個鏈表存儲，比如在處理多項式的加減法時就需要將兩個多項式的數據進行合并。合并方式有很多種：如果按照存儲方式的不同，可以將兩個鏈表的數據分別提取出來生成一個新的鏈表來存儲原先兩個鏈表的數據，還可以將其中一個鏈表的數據依次插入到另外一個鏈表的相應位置當中去。在遇到相同數據時可以采取只留下一個數據的方式和兩個數據均保留的方式。這些不同點需要到具體的問題中具體分析，但是只是在細節上有一些差別，大體的思路都是一樣的，本文主要介紹將一個鏈表插入到另一個鏈表的相應位置，插入完成后銷毀鏈表二，且遇到相同數據采用均保留的方式。

我們還是先拋開鏈表的操作本身，先對兩組不同的數據進行合并操作，知道兩組按升序排列的數據該如何合并成一組數據，我們來分析這樣幾組數據（將第二組的數據插入到第一組中）：

1   5   9   13   15

2   7   12

對于這組數據我們可以很輕易的說出應該把“2”插入到“1”的前面，應該把“7”插入到“5”的前面... ... 那么我們又是如何得到這個結論的呢，接下來我們來用語言細致的描述一下我們剛才是如何得到這樣的結論的：“首先，遍歷第一組數據，找到第一個比要插入的數據大的數據的前一個數據“i”，再將要插入的數據插入到“i”的后面”。

上述描述解決了插入數據的一般性情況，包括我們用“比該數據大”這樣的話說明了遇到相同數據時該如何處理，但是，問題依然存在，我們來觀察下面一組數據：

2   4   7   9

1   3   6   8

我們要將第二組數據插入到第一組數據中，按照之前的說法，找到第一個不比待插入數據小的數據的前一個數據“i”，但是我們發現第一組數據中第一個數據就符合我們的要求，那么它自然沒有前一個數據。這里我們給出一個方案：在進行插入工作前，先對兩個鏈表的首元素進行比較，如果鏈表一的首元素是小于第二個鏈表的首元素的，那么開始合并工作，如果鏈表一的首元素不小于第二個鏈表的首元素，我們先交換兩個鏈表的頭結點，使得鏈表一變成鏈表二。但是這種方式僅適用于我們當前的情況，因為我們要實現的是將鏈表二的元素加入到鏈表一中，之后銷毀鏈表二，這就意味著我們最后只要得到一個鏈表就可以，只要使得傳遞過來的鏈表一在執行完我們的合并鏈表程序后能夠變成合并后的結果鏈表就好了，因此我們可能要更改傳遞過來的鏈表的頭結點的值。

根據上面的說法，我們就要在開始進行合并之前先對兩個鏈表的首元素進行比較，如果鏈表二的首元素比鏈表一的首元素大，則交換兩個鏈表的控制頭，再執行后續的合并工作。

解決了上述問題，還差最后一種情況，我們來觀察下面一組數據：

1   3   4   6   7

2   6   9   10  13

我們可以觀察到，將第二組數據依次向第一組數據中插入，到了“9”的時候，第一組數據就沒有可以插入的位置了，而應該在尾部追加，于是，我們就不能執行之前的操作了，而應該執行另外一項操作，我們具體實現是這樣的：

如果我們在第一組數據中找不到比待插入數據大的數據，我們就將待插入數據的后面的數據連同待插入數據本身，追加到第一組數據的末尾。

根據如上分析，我們需要執行的有四種對鏈表的操作：1、在指定鏈中找到第一個比目標數據的大的節點的前驅節點； 2、將指定元素插入到指定鏈表的指定位置； 3、將鏈表中的制定位置后的所有元素追加到指定鏈表的末尾； 4、交換兩個鏈表的頭結點。

下面我們就分布解決這四種操作（注：A_LINE是我們自己定義的為了方便起見的一個結構體，只有一個int類型的num和一個A_LINE *類型的next成員不具有任何意義，僅僅是為了完成合并鏈表）：

1、在指定鏈中找到第一個比目標數據的大的節點的前驅節點：

A_LINE *getFirstLocalBiggerThanEle(A_LINE head, A_LINE ele) {
 A_LINE *p;
 A_LINE *q;
 
 for (p = head.next; p->next != NULL && ele.num >= p->num; p = p->next)
 q = p;
 if (p->next == NULL) {
 return NOT_FOUND;
 }
 return q;
}

我們用A_LINE *p來遍歷鏈表一，用A_LINE *q來實時保存當前節點的前驅節點，鏈表沒有遍歷完而且當前元素依然小于等于目標元素，則循環繼續。當循環結束后，判斷循環結束的原因，如果是因為鏈表遍歷完了而結束的循環，則說明整個鏈表里都沒有比目標節點大的節點，返回NOT_FOUND;若是因為找到了比目標元素大的元素而結束的，那么返回該元素的前驅節點的地址“q”。

2、將指定元素插入到指定鏈表的指定位置：

void insertEleToLine(A_LINE *local, A_LINE ele) {
 A_LINE *newEle;
 
 newEle = (A_LINE *)calloc(1, sizeof(A_LINE));
 newEle->next = local->next;
 local->next = newEle;
 newEle->num = ele.num;
}

在第一步中我們已經可以得到需要插入的位置的首地址了，下一步我們就要完成插入了，這對于學過鏈表的人并不是什么難事，本文不做為重點講解。

3、將一段數據追加到指定鏈表的末尾：

void appendLineToLineEnd(A_LINE *line, A_LINE targetLine) {
 A_LINE *tarP;
 
 for (tarP = targetLine.next; tarP->next != NULL; tarP = tarP->next)
 ;
 tarP->next = line;
}

這里給出的A_LINE *line代表著待插入鏈表的首元素的首地址，targetLine代表要插入到的鏈表的頭結點。首先先定位目標鏈表的末節點的首地址，再將待插入鏈表的末節點的next成員更改為待插入鏈表的首元素的首地址。

但這里存在著問題，這里的賦值相當于直接把鏈表二的一部分節點直接放到鏈表一的末尾，并不是復制出來一份再追加到鏈表一的末尾，這樣就使得鏈表二的那一部分節點又屬于鏈表一又屬于鏈表二，而鏈表二在最后是要被釋放的，那么它的后幾個節點也會被釋放。為了防止這樣的情況發生，我們必須將鏈表二中的要插入到鏈表一中的那一部分節點的前驅節點的next成員賦值為NULL，這樣在就相當于將那一部分節點從鏈表二中刪除，但是這樣并不會引起內存泄漏，這些節點被連接到了鏈表一的末尾，因此在釋放鏈表一的時候這些節點依然會被釋放。

4、交換兩個鏈表的頭結點：

void exchangeLine(A_LINE *head1, A_LINE *head2) {
 A_LINE temp;
 
 temp = *head1;
 *head1 = *head2;
 *head2 = temp;
}

5、合并鏈表完整代碼：

void margeLine(A_LINE *targetLine, A_LINE *resourceLine) {
 A_LINE *tarP = targetLine->next;
 A_LINE *srcP = resourceLine->next;
 A_LINE *srcPreP;
 A_LINE *local;
 
 if (tarP->num >= srcP->num) {
 exchangeLine(targetLine, resourceLine);
 }
 
 for (srcP = srcPreP = resourceLine->next; srcP != NULL; srcP = srcP->next) {
 local = getFirstLocalBiggerThanEle(*targetLine, *srcP);
 
 if (local != NOT_FOUND) {
 insertEleToLine(local, *srcP);
 }
 else {
 appendLineToLineEnd(srcPreP->next, *targetLine);
 srcPreP->next = NULL;
 destoryLine(resourceLine);
 return;
 }
 srcPreP = srcP;
 }
 destoryLine(resourceLine);
}

最后我們給出整體的可測試的代碼：

#include<stdio.h>
#include<malloc.h>
 
#define NOT_FOUND NULL
 
typedef struct A_LINE {
 int num;
 struct A_LINE *next;
} A_LINE;
 
void margeLine(A_LINE *targetLine, A_LINE *resourceLine);
A_LINE *getFirstLocalBiggerThanEle(A_LINE head, A_LINE ele);
void insertEleToLine(A_LINE *local, A_LINE ele);
void destoryLine(A_LINE *head);
void initLine(A_LINE *head);
void showLine(A_LINE head);
void exchangeLine(A_LINE *head1, A_LINE *head2);
void appendLineToLineEnd(A_LINE *line, A_LINE targetLine);
 
void appendLineToLineEnd(A_LINE *line, A_LINE targetLine) {
 A_LINE *tarP;
 
 for (tarP = targetLine.next; tarP->next != NULL; tarP = tarP->next)
 ;
 tarP->next = line;
}
 
void exchangeLine(A_LINE *head1, A_LINE *head2) {
 A_LINE temp;
 
 temp = *head1;
 *head1 = *head2;
 *head2 = temp;
}
 
void showLine(A_LINE head) {
 A_LINE *p;
 
 for (p = head.next; p != NULL; p = p->next) {
 printf("%d ", p->num);
 }
}
 
void initLine(A_LINE *head) {
 int num;
 A_LINE *p = NULL;
 
 printf("請輸入一個數（-1表示結束）：");
 scanf_s("%d", &num);
 while (num != -1) {
 if (head->next == NULL) {
 head->next = (A_LINE *)calloc(1, sizeof(A_LINE));
 (head->next)->num = num;
 p = head->next;
 }
 else {
 p->next = (A_LINE *)calloc(1, sizeof(A_LINE));
 (p->next)->num = num;
 p = p->next;
 }
 printf("請輸入一個數（-1表示結束）");
 scanf_s("%d", &num);
 }
}
 
void destoryLine(A_LINE *head) {
 A_LINE *p = head->next;
 
 while (NULL != head->next) {
 p = head->next;
 head->next = p->next;
 free(p);
 }
}
 
void insertEleToLine(A_LINE *local, A_LINE ele) {
 A_LINE *newEle;
 
 newEle = (A_LINE *)calloc(1, sizeof(A_LINE));
 newEle->next = local->next;
 local->next = newEle;
 newEle->num = ele.num;
}
 
A_LINE *getFirstLocalBiggerThanEle(A_LINE head, A_LINE ele) {
 A_LINE *p = NULL;
 A_LINE *q = NULL;
 
 for (p = head.next; p != NULL && ele.num >= p->num; p = p->next)
 q = p;
 if (p == NULL) {
 return NOT_FOUND;
 }
 return q;
}
 
void margeLine(A_LINE *targetLine, A_LINE *resourceLine) {
 A_LINE *tarP = targetLine->next;
 A_LINE *srcP = resourceLine->next;
 A_LINE *srcPreP;
 A_LINE *local;
 
 if (tarP->num >= srcP->num) {
 exchangeLine(targetLine, resourceLine);
 }
 
 for (srcP = srcPreP = resourceLine->next; srcP != NULL; srcP = srcP->next) {
 local = getFirstLocalBiggerThanEle(*targetLine, *srcP);
 
 if (local != NOT_FOUND) {
 insertEleToLine(local, *srcP);
 }
 else {
 appendLineToLineEnd(srcPreP->next, *targetLine);
 srcPreP->next = NULL;
 destoryLine(resourceLine);
 return;
 }
 srcPreP = srcP;
 }
 destoryLine(resourceLine);
}
 
void main(void) {
 A_LINE head1 = {0};
 A_LINE head2 = {0};
 
 printf("錄入第一個鏈表：\n");
 initLine(&head1);
 printf("錄入第二個鏈表\n");
 initLine(&head2);
 
 margeLine(&head1, &head2);
 
 printf("鏈表一:\n");
 showLine(head1);
 printf("鏈表二:\n");
 showLine(head2);
 
  destoryLine(&head1);
}

關于“C語言如何合并兩個帶頭節點升序排列鏈表”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。