【雙向鏈表】
①.建立一個雙向鏈表？
1 typedef struct DbNode
2 {
3 int data; //節點數據
4 DbNode *left; //前驅節點指針
5 DbNode *right; //後繼節點指針
6 } DbNode;
（1）建立雙向鏈表：為方便，這裡定義了三個函數：
q CreateNode()根據數據來創建一個節點，返回新創建的節點。
q CreateList()函數根據一個節點數據創建鏈表的表頭，返回表頭節點。
q AppendNode ()函數總在表尾插入新節點（其內部調用CreateNode()生成節點），返回表頭節點。
1 //根據數據創建創建節點
2 DbNode *CreateNode(int data)
3 {
4 DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));
5 pnode->data = data;
6 pnode->left = pnode->right = pnode; //創建新節點時
7 //讓其前驅和後繼指針都指向自身
8 return pnode;
9}
10
11 //創建鏈表
12 DbNode *CreateList(int head) //參數給出表頭節點數據
13 { //表頭節點不作為存放有意義數據的節點
14 DbNode *pnode = (DbNode *)malloc(sizeof(DbNode));
15 pnode->data = head;
16 pnode->left = pnode->right = pnode;
17
18 return pnode;
19 }
20
21 //插入新節點,總是在表尾插入; 返回表頭節點
22 DbNode *AppendNode(DbNode *head, int data) //參數1是鏈表的表頭節點，
23 { //參數2是要插入的節點,其數據為data
24 DbNode *node = CreateNode(data); //創建數據為data的新節點
25 DbNode *p = head, *q;
26
27 while(p != NULL)
28 {
29 q = p;
30 p = p->right;
31 }
32 q->right = node;
33 node->left = q;
34
35 return head;
36 }
我們可以使用其中的CreateList()和AppendNode()來生成一個鏈表，下面是一個數據生成從0到9含有10個節點的循環鏈表。
1 DbNode *head = CreateList(0); //生成表頭，表頭數據為0
2
3 for (int i = 1; i < 10; i++)
4 {
5 head = AppendNode(head, i); //添加9個節點，數據為從1到9
6 }
②.計算雙向鏈表長度？（或者打印）
為了得到雙向鏈表的長度，需要使用right指針進行遍歷，直到得到NULL為止。
1 //獲取鏈表的長度
2 int GetLength(DbNode *head) //參數為鏈表的表頭節點
3 {
4 int count = 1;
5 DbNode *pnode = NULL;
6
7 if (head == NULL) //head為NULL表示鏈表空
8 {
9 return 0;
10 }
11 pnode = head->right;
12 while (pnode != NULL)
13 {
14 pnode = pnode->right; //使用right指針遍歷
15 count++; ///// 也可以打印
16 }
17
18 return count;
19 }
③.查找雙向鏈表節點？
使用right指針遍歷，直至找到數據為data的節點，如果找到節點，返回節點，否則返回NULL。
1 //查找節點，成功則返回滿足條件的節點指針，否則返回NULL
2 DbNode *FindNode(DbNode *head, int data) //參數1是鏈表的表頭節點
3 { //參數2是要查找的節點,其數據為data
4 DbNode *pnode = head;
5
6 if (head == NULL) //鏈表為空時返回NULL
7 {
8 return NULL;
9 }
10
11 /*找到數據或者到達鏈表末尾退出while循環*/
12 while (pnode->right != NULL && pnode->data != data)
13 {
14 pnode = pnode->right; //使用right指針遍歷
15 }
16
17 //沒有找到數據為data的節點，返回NULL
18 if (pnode->right == NULL)
19 {
20 return NULL;
21 }
22
23 return pnode;
24 }
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
【單向鏈表】
①.如何創建一個單鏈表？
鏈表節點的定義：
typedef struct node
{
int data; //節點內容
node *next; //下一個節點
}node;
單鏈表的創建：
1 //創建單鏈表
2 node *create()
3 {
4 int i = 0; //鏈表中數據的個數
5 node *head, *p, *q;
6 int x = 0;
7 head = (node *)malloc(sizeof(node)); //創建頭節點
8
9 while(1)
10 {
11 printf("Please input the data: ");
12 scanf("%d", &x);
13 if (x == 0) //data為0時創建結束
14 break;
15 p = (node *)malloc(sizeof(node));
16 p->data = x;
17 if (++i == 1)
18 { //鏈表只有一個元素
19 head->next = p; //連接到head的後面
20 }
21 else
22 {
23 q->next = p; //連接到鏈表尾端
24 }
25 q = p; //q指向末節點
26 }
27 q->next = NULL; //鏈表的最後一個指針為NULL
28 return head;
29 }
上面的代碼中，使用while循環每次從終端讀入一個整型數據，並調用malloc動態分配鏈表節點內存存儲這個整型數據，然後再插入到單鏈表的末尾。最後當數據為0時表示插入數據結束，此時把末尾節點的next指針置為NULL。
②.查找單鏈表中間元素？
解析：
這裡使用一個只用一遍掃描的方法。描述如下：
假設mid指向當前已經掃描的子鏈表的中間元素，cur指向當前以掃描鏈表的尾節點，那麼繼續掃描即移動cur到cur->next,這時只需判斷一下應不應移動mid到mid->next就行了。所以一遍掃描就能找到中間位置。代碼如下：
1 node *search(node *head)
2 {
3 int i = 0;
4 int j = 0;
5 node *current = NULL;
6 node *middle = NULL;
7
8 current = middle = head->next;
9 while(current != NULL)
10 {
11 if( i / 2 > j)
12 {
13 j++;
14 middle = middle->next;
15 }
16 i++;
17 current = current->next;
18 }
19
20 return middle;
21 }
③.打印單向鏈表？
解析：
單鏈表的打印：
1 //打印單鏈表
2 void print(node *head)
3 {
4 node *p;
5 int index = 0;
6 if (head->next == NULL) //鏈表為空
7 {
8 printf("Link is empty!\n");
9 return;
10 }
11 p = head->next;
12 while(p != NULL) //遍歷鏈表
13 {
14 printf("The %dth node is: %d\n", ++index, p->data); //打印元素 ----- 也可計算單鏈表長度 count++；
15 p = p->next;
16 }
17 }
單鏈表的打印與單鏈表的測長方法類似，使用while循環進行遍歷鏈表所有節點並打印各個節點內容，當遇到NULL時結束循環。
④.查找單鏈表節點？
單鏈表的查找節點：
1 //查找單鏈表pos位置的節點,返回節點指針
2 //pos從0開始,0返回head節點
3 node *search_node(node *head, int pos)
4 {
5 node *p = head->next;
6 if (pos < 0) //pos位置不正確
7 {
8 printf("incorrect position to search node!\n");
9 return NULL;
10 }
11 if (pos == 0) //在head位置，返回head
12 {
13 return head;
14 }
15 if(p == NULL)
16 {
17 printf("Link is empty!\n"); //鏈表為空
18 return NULL;
19 }
20
21 while(--pos)
22 {
23 if ((p = p->next) == NULL)
24 { //超出鏈表返回
25 printf("incorrect position to search node!\n");
26 break;
27 }
28 }
29 return p;
30 }
⑤.單鏈表插入節點？
解析：
向單鏈表中某個位置（第pos個節點）之後插入節點，這裡分為插入到鏈表首部、插入到鏈表中間，以及鏈表尾端三種情況：
1 //在單鏈表pos位置處插入節點，返回鏈表頭指針
2 //pos從0開始計算,0表示插入到head節點後面
3 node *insert_node(node *head, int pos, int data)
4 {
5 node *item = NULL;
6 node *p;
7
8 item = (node *)malloc(sizeof(node));
9 item->data = data;
10 if (pos == 0) //插入鏈表頭後面
11 {
12 head->next = item; //head後面是item
13 return head;
14 }
15 p = search_node(head, pos); //獲得位置pos的節點指針
16 if (p != NULL)
17 {
18 item->next = p->next; //item指向原pos節點的後一個節點
19 p->next = item; //把item插入到pos的後面
20 }
21 return head;
22 }
⑥.單向鏈表刪除節點？
解析：
單鏈表刪除節點：
1 //刪除單鏈表的pos位置的節點，返回鏈表頭指針
2 //pos從1開始計算，1表示刪除head後的第一個節點
3 node *delete_node(node *head, int pos)
4 {
5 node *item = NULL;
6 node *p = head->next;
7 if (p == NULL) //鏈表為空
8 {
9 printf("link is empty!\n");
10 return NULL;
11 }
12 p = search_node(head, pos-1); //獲得位置pos的節點指針
13 if (p != NULL && p->next != NULL)
14 {
15 item = p->next;
16 p->next = item->next;
17 delete item;
18 }
19 return head;
20 }
⑦.單向鏈表的逆序？
解析：
這是一個經常被問到的面試題，也是一個非常基礎的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過逆置後成為5->4->3->2->1。
最容易想到的方法是遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然後將當前節點元素的指針反轉後，利用已經存儲的指針往後面繼續遍歷。
1 node *reverse(node *head)
2 {
3 node *p, *q, *r;
4
5 if (head->next == NULL) //鏈表為空
6 {
7 return head;
8 }
9
10 p = head->next;
11 q = p->next; //保存原第二個節點
12 p->next = NULL; //原第一個節點為末節點
13
14 while(q != NULL) //遍歷，各個節點的next指針反轉
15 {
16 r = q->next;
17 q->next = p;
18 p = q;
19 q = r;
20 }
21 head->next = p; //新的第一個節點為原末節點
22 return head;
23 }
⑧.單鏈表的正向排序？
解析：
下面試結構體定義和代碼如下：
1 typedef struct node
2 {
3 int data;
4 node *next;
5 }node;
6
7 node* InsertSort(void)
8 {
9 int data = 0;
10 struct node *head=NULL,*New,*Cur,*Pre;
11 while(1)
12 {
13 printf("please input the data\n");
14 scanf("%d", &data);
15 if (data == 0) //輸入0結束
16 {
17 break;
18 }
19 New=(struct node*)malloc(sizeof(struct node));
20 New->data = data; //新分配一個node節點
21 New->next = NULL;
22 if(head == NULL)
23 { //第一次循環時對頭節點賦值
24 head=New;
25 continue;
26 }
27 if(New->data <= head->data)
28 {//head之前插入節點
29 New->next = head;
30 head = New;
31 continue;
32 }
33 Cur = head;
34 while(New->data > Cur->data && //找到需要插入的位置
35 Cur->next!=NULL)
36 {
37 Pre = Cur;
38 Cur = Cur->next;
39 }
40 if(Cur->data >= New->data) //位置在中間
41 { //把new節點插入到Pre和cur之間
42 Pre->next = New;
43 New->next = Cur;
44 }
45 else //位置在末尾
46 Cur->next = New; //把new節點插入到cur之後
47 }
48 return head;
49 }
⑨.有序單鏈表的合並？
已知兩個鏈表head1 和head2 各自有序，請把它們合並成一個鏈表依然有序。使用非遞歸方法以及遞歸方法。
解析：
首先介紹非遞歸方法。因為兩個鏈表head1 和head2都是有序的，所以我們只需要找把較短鏈表的各個元素有序的插入到較長的鏈表之中就可以了。
源代碼如下：
1 node* insert_node(node *head, node *item) //head != NULL
2 {
3 node *p = head;
4 node *q = NULL; //始終指向p之前的節點
5
6 while(p->data < item->data && p != NULL)
7 {
8 q = p;
9 p = p->next;
10 }
11 if (p == head) //插入到原頭節點之前
12 {
13 item->next = p;
14 return item;
15 }
16 //插入到q與p之間之間
17 q->next = item;
18 item->next = p;
19 return head;
20 }
21
22 /* 兩個有序鏈表進行合並 */
23 node* merge(node* head1, node* head2)
24 {
25 node* head; //合並後的頭指針
26 node *p;
27 node *nextP; //指向p之後
28
29 if ( head1 == NULL ) //有一個鏈表為空的情況，直接返回另一個鏈表
30 {
31 return head2;
32 }
33 else if ( head2 == NULL )
34 {
35 return head1;
36 }
37
38 // 兩個鏈表都不為空
39 if(length(head1) >= length(head2)) //選取較短的鏈表
40 { //這樣進行的插入次數要少些
41 head = head1;
42 p = head2;
43 }
44 else
45 {
46 head = head2;
47 p = head1;
48 }
49
50 while(p != NULL)
51 {
52 nextP = p->next; //保存p的下一個節點
53 head = insert_node(head, p); //把p插入到目標鏈表中
54 p = nextP; //指向將要插入的下一個節點
55 }
56
57 return head;
58 }
這裡insert_node()函數是有序的插入節點，注意與前面例題中的函數有區別，這裡它傳入的參數是node*類型。然後在merge()函數中（代碼52~55行）循環把短鏈表中的所有節點插入到長鏈表中。
接下來介紹非遞歸方法。比如有下面兩個鏈表：
鏈表1：1->3->5
鏈表2：2->4->6
遞歸方法的步驟如下：
（1）比較鏈表1和鏈表2的第一個節點數據，由於1<2，因此把結果鏈表頭節點指向鏈表1中的第一個節點，即數據1所在的節點。
（2）對剩余的鏈表1（3->5）和鏈表2再調用本過程，比較得到結果鏈表的第二個節點，即2與3比較得到2。此時合並後的鏈表節點為1->2。
接下來的過程類似（2），如此遞歸知道兩個鏈表的節點都被加到結果鏈表中。
1 node * MergeRecursive(node *head1, node *head2)
2 {
3 node *head = NULL;
4
5 if (head1 == NULL)
6 {
7 return head2;
8 }
9 if (head2 == NUL)
10 {
11 return head1;
12 }
13
14 if ( head1->data < head2->data )
15 {
16 head = head1 ;
17 head->next = MergeRecursive(head1->next,head2);
18 }
19 else
20 {
21 head = head2 ;
22 head->next = MergeRecursive(head1,head2->next);
23 }
24
25 return head ;
26 }
下面是測試程序：
1 int main()
2 {
3 node *head1 = create(); //創建單鏈表1
4 node *head2 = create(); //創建單鏈表2
5 //node *head = merge(head1, head2);
6 node *head = MergeRecursive(head1, head2);
7 print(head);
8
9 return 0;
10 }
這裡使用merge()函數和MergeRecursive()函數測試，結果一致。
作者“志在千裡”
