合并两个有序的单链表

【说明】：

本文是左程云老师所著的《程序员面试代码指南》第二章中“合并两个有序的单链表”这一题目的C++复现。

本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

感谢左程云老师的支持。

【题目】：

给定两个有序单链表的头节点 head1 和 head2，请合并两个有序链表，合并后的链表依然有序，并返回合并后链表的头节点。

例如：

0->2->3->7->NULL

1->3->5->7->9->NULL

合并后的链表为：0->1->2->3->3->5->7->7->9->NULL

【思路】：

解法：以头节点较小的链表为基准，将另一个链表插入到此链表中。

【编译环境】：

CentOS6.7（x86_64）

gcc 4.4.7

【实现】：

实现及测试代码：

1 /*
 2  *文件名：list_merge.cpp
 3  *作者：
 4  *摘要：合并两个有序的单链表
 5  */
 6 
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 class Node 
12 {
13 public:
14     Node(int data)
15     {
16         value = data;
17         next = NULL;
18     }
19 public:
20     int value;
21     Node *next;
22 };
23 
24 Node* merge(Node *head1,Node *head2)
25 {
26     if(NULL == head1 || NULL == head2)
27         return NULL != head1 ? head1 : head2;
28     Node *head = head1->value < head2->value ? head1 : head2;
29     Node *cur1 = head == head1 ? head1 : head2;
30     Node *cur2 = head == head1 ? head2 : head1;
31     Node *pre = NULL;
32     Node *next = NULL;
33 
34     while(NULL != cur1 && NULL != cur2)
35     {
36         if(cur1->value <= cur2->value)    //以cur1 为基准，将cur2插入到cur1中
37         {
38             pre = cur1;
39             cur1 = cur1->next;
40         }
41         else    //将第二个链表的节点插入到第一个链表中
42         {
43             next = cur2->next;
44             pre->next = cur2;
45             cur2->next = cur1;
46             pre = cur2;
47             cur2 = next;
48         }
49     }
50     pre->next = NULL == cur1 ? cur2 : cur1;
51     return head;
52 }
53 
54 void printList(Node *head)
55 {
56     while(NULL != head)
57     {
58         cout << head->value << " ";
59         head = head->next;
60     }
61     cout << endl;
62 }
63 
64 int main()
65 {
66     Node *head1(NULL),*ptr1(NULL);
67     Node *head2(NULL),*ptr2(NULL);    
68     for(int i =1;i<10;i += 2)//构造链表
69     {
70         if(NULL == head1)
71         {    
72             head1 = new Node(i);
73             ptr1 = head1;
74             continue;
75         }
76         ptr1->next = new Node(i);
77         ptr1 = ptr1->next;    
78     }
79     for(int i =1;i<10;i += 2)//构造链表
80     {
81         if(NULL == head2)
82         {    
83             head2 = new Node(i);
84             ptr2 = head2;
85             continue;
86         }
87         ptr2->next = new Node(i);
88         ptr2 = ptr2->next;    
89     }
90     cout << "Before merging (head1):" << endl;
91     printList(head1);
92     cout << "Before merging (head2):" << endl;
93     printList(head2);
94     cout << "After merging:" << endl;
95     Node *head = merge(head1,head2);
96     printList(head);
97     return 0;
98 }

View Code

注：

转载请注明出处；

转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5450018.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍