【剑指offer】面试题17、合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。例如输入图中的链表 1 和链表 2，则合并之后的升序链表如链表 3 所示。链表结点定义如下：
typedef struct Node
{
    int m_nValue;
    struct Node *m_pNext;
}ListNode;

一、创建有序链表

创建有序链表的一般步骤：
1、初始化链表为空；
2、生成新的结点指针 pNew；
3、找到该结点值对应的位置，有两种可能：头部，非头部；
4、插入该结点。

假设一链表L现在两个结点，结点值分别为 3、5，现在欲插入的结点值分别为 4,7：

1、现在我们欲插入值为 4 的结点pNew，遍历指针为 pNode，初始值指向值为 3 的头结点pHead；

2、遍历原有链表 L 时，发现 4 > 3，于是 pNode 变为指向值为5的结点pTail；

3、继续比较，由于5 > 4，因此值为 5 的结点的位置就是我们要找的位置；

4、执行插入操作；

注意：在插入的过程中，由于需要连接链表，需要把pNode的前一个链表结点保存下来。

代码如下：

 1 void createOrderedList(ListNode **pHead, int len)
 2 {
 3     while(len--)
 4     {
 5         ListNode *pNew = (ListNode*)malloc(sizeof(ListNode));
 6         pNew->m_nValue = rand()%100;
 7         pNew->m_pNext = NULL;
 8 
 9         if(*pHead == NULL) // 空
10             *pHead = pNew;
11         else //非空
12         {
13             ListNode *pNode = *pHead;
14             ListNode *pPre = NULL;
15             while(pNode != NULL)
16             {
17                 if(pNode->m_nValue < pNew->m_nValue)
18                 {
19                     pPre = pNode;
20                     pNode = pNode->m_pNext;
21                 }
22                 else
23                     break;
24             }
25             // 插入的位置
26             if(pPre == NULL) // 头结点位置
27             {
28                 pNew->m_pNext = *pHead;
29                 *pHead = pNew;
30             }
31             else // 其他位置
32             {
33                 pNew->m_pNext = pNode; // 连接链表
34                 pPre->m_pNext = pNew;
35             }
36         }
37     }
38 }

View Code

二、两个有序链表的合并(顺序从小到大依次排列)

思路：设有 X 和 Y两个链表；

1、分别遍历 X和Y这两个链表；

2、若 Px 的结点值小于 Py 的结点值，则将结点 Px 结点放入到合并之后的链表中；否则，执行3；

3、将结点 Px 结点放入到合并之后的链表中；

4、若while循环中 Px==NULL，则说明链表Px已空，这时，直接将Py的后续结点加入到链表中即可；

5、反之，若while循环中 Py==NULL，则说明链表Py已空，这时，直接将Px的后续结点加入到链表中即可。

完整的代码如下：

  1 #include "stdio.h"
  2 #include "stdlib.h"
  3 #include "time.h"
  4 
  5 #define N 10
  6 
  7 typedef struct Node
  8 {
  9     int m_nValue;
 10     struct Node *m_pNext;
 11 }ListNode, *pListNode;
 12 
 13 // 创建有序链表
 14 void createOrderedList(ListNode **pHead, int len)
 15 {
 16     while(len--)
 17     {
 18         ListNode *pNew = (ListNode*)malloc(sizeof(ListNode));
 19         pNew->m_nValue = rand()%100;
 20         pNew->m_pNext = NULL;
 21 
 22         if(*pHead == NULL) // 空
 23             *pHead = pNew;
 24         else //非空
 25         {
 26             ListNode *pNode = *pHead;
 27             ListNode *pPre = NULL;
 28             while(pNode != NULL)
 29             {
 30                 if(pNode->m_nValue < pNew->m_nValue)
 31                 {
 32                     pPre = pNode;
 33                     pNode = pNode->m_pNext;
 34                 }
 35                 else
 36                     break;
 37             }
 38             // 插入的位置
 39             if(pPre == NULL) // 头结点位置
 40             {
 41                 pNew->m_pNext = *pHead;
 42                 *pHead = pNew;
 43             }
 44             else // 其他位置
 45             {
 46                 pNew->m_pNext = pNode;
 47                 pPre->m_pNext = pNew;
 48             }
 49         }
 50     }
 51 }
 52 
 53 void printList(ListNode *pHead)
 54 {
 55     while(pHead != NULL)
 56     {
 57         printf("%3d ", pHead->m_nValue);
 58         pHead = pHead->m_pNext;
 59     }
 60     printf("
");
 61 }
 62 
 63 // 合并有序链表
 64 ListNode *Merge(ListNode *leftHead, ListNode *rightHead)
 65 {
 66     if(!leftHead)
 67         return rightHead;
 68     else if(!rightHead)
 69         return leftHead;
 70 
 71     ListNode *mergeHead, *mergeTail;
 72     mergeHead = mergeTail = NULL;
 73     ListNode *pLeft = leftHead;
 74     ListNode *pRight = rightHead;
 75     while(pLeft != NULL && pRight != NULL)
 76     {
 77         if(pLeft->m_nValue < pRight->m_nValue) // 左链表结点值比右链表结点值大
 78         {
 79             if(mergeHead == NULL) // 头结点
 80             {
 81                 mergeHead = mergeTail = pLeft;
 82             }
 83             else // 非头结点
 84             {
 85                 mergeTail->m_pNext = pLeft;
 86                 mergeTail = pLeft;
 87             }
 88             pLeft = pLeft->m_pNext;
 89         }
 90         else// 右链表结点值比左链表结点值大
 91         {
 92             if(mergeHead == NULL) // 头结点
 93             {
 94                 mergeHead = mergeTail = pRight;
 95             }
 96             else // 非头结点
 97             {
 98                 mergeTail->m_pNext = pRight;
 99                 mergeTail = pRight;
100             }
101             pRight = pRight->m_pNext;
102         }
103 
104     }
105 
106     if(pLeft != NULL)
107         mergeTail->m_pNext = pLeft;
108     if(pRight != NULL)
109         mergeTail->m_pNext = pRight;
110 
111     return mergeHead;
112 }
113 
114 int main(int argc, char const *argv[])
115 {
116     srand(time(NULL));
117 
118     ListNode *pHead1 = NULL;
119     ListNode *pHead2 = NULL;
120 
121     createOrderedList(&pHead1, N);
122     printf("List1: ");
123     printList(pHead1);
124 
125     createOrderedList(&pHead2, N);
126     printf("List2: ");
127     printList(pHead2);
128 
129     ListNode *pMergeHead = Merge(pHead1, pHead2);
130     if(pMergeHead != NULL)
131     {
132         printf("The Merge Node: %d
", pMergeHead->m_nValue);
133     }
134     printf("MergedList: ");
135     printList(pMergeHead);
136 
137     return 0;
138 }

View Code

本文完。