剑指offer 合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：建立一个头节点，设两个指针，分别指向两个排好序的链表头，比较大小。

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
12     {
13         ListNode *pMerge = new ListNode (0), *tmp = pMerge; //tmp指向pMerge链表的尾结点
14         ListNode *tmp1 = pHead1, *tmp2 = pHead2; //设置两个临时指针，使得pHead1, pHead2指向不变
15         while (tmp1 != NULL && tmp2 != NULL) {
16             // 如果第一个链表的头结点值小于第二个链表的头结点值，将第一个链表的头结点放入pMerge链表的尾部
17             if (tmp1->val < tmp2->val) { 
18                 tmp->next = tmp1;
19                 tmp = tmp1;
20                 tmp1 = tmp1->next;
21             } else {
22                 tmp->next = tmp2;
23                 tmp = tmp2;
24                 tmp2 = tmp2->next;
25             }
26             tmp->next = NULL; //始终保持合并后的链表尾指向空
27         }
28         if (tmp1 != NULL) {
29             tmp->next = tmp1;
30         } else {
31             tmp->next = tmp2;
32         }
33         return pMerge->next;
34     }
35 };

以下是不建立头结点的做法:

 1 class Solution {
 2 public:
 3     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 4     {
 5         //下面这两个判断很重要，否则后面的current->next很容易出现段错误
 6         if (pHead1 == NULL) {
 7             return pHead2;
 8         } 
 9         if (pHead2 == NULL) {
10             return pHead1;
11         }
12         ListNode *pMerge = NULL;
13         ListNode *current = pMerge, *tmp1 = pHead1, *tmp2 = pHead2;
14         while (tmp1 != NULL && tmp2 != NULL) {
15             if (tmp1->val < tmp2->val) {
16                 if (current == NULL) {
17                     current = pMerge = tmp1;
18                 } else {
19                     current->next = tmp1;
20                     current = tmp1;
21                 }
22                 tmp1 = tmp1->next;
23             } else {
24                 if (current == NULL) {
25                     current = pMerge = tmp2;
26                 } else {
27                     current->next = tmp2;
28                     current = tmp2;
29                 }
30                 tmp2 = tmp2->next;
31             }
32             current->next = NULL;
33         }
34         if (tmp1 != NULL) {
35             current->next = tmp1;
36         } else {
37             current->next = tmp2;
38         }
39         return pMerge;
40     }
41 };

可以看到第一个while循环中每次都要判断是不是第一个结点，如果是第一个结点，就把它当作链表第一个结点，而不是链表的下一个结点。加了一个判断，更耗时。

以上都是非递归解法,下面是一个递归解法：

 1 class Solution {
 2 public:
 3     ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
 4     {
 5         if (pHead1 == NULL) {
 6             return pHead2;
 7         }
 8         if (pHead2 == NULL) {
 9             return pHead1;
10         }
11         if (pHead1->val < pHead2->val) {
12             pHead1->next = Merge(pHead1->next, pHead2);
13             return pHead1;
14         } else {
15             pHead2->next = Merge(pHead1, pHead2->next);
16             return pHead2;
17         }
18     }
19 };