C++刷剑指offer(面试题25. 合并两个排序的链表）【链表】

糖逗

题目描述：

1. 
   
2. 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
   
3. 
   
4. 示例1：
   
5. 
   
6. 输入：1->2->4, 1->3->4
   
7. 输出：1->1->2->3->4->4
   
8. 限制：
   
9. 
   
10. 0 <= 链表长度 <= 1000

复制代码

1. #include <iostream>
   
2. 
   
3. 
   
4. using namespace std;
   
5. 
   
6. struct ListNode{
   
7.         int value;
   
8.         ListNode* next;
   
9.         ListNode(int x): value(x), next(NULL){
   
10.                
    
11.         }
    
12. };
    
13. 
    
14. void printList(ListNode* input){
    
15.         ListNode* temp = input;
    
16.         while(temp -> next){
    
17.                 temp = temp -> next;
    
18.                 cout << temp -> value << " ";       
    
19.         }
    
20.         cout << endl;
    
21.         cout << "-------------" << endl;
    
22.        
    
23. }
    
24. 
    
25. 
    
26. ListNode* solution(ListNode* input1, ListNode* input2){
    
27.         ListNode* temp1 = input1 -> next;
    
28.         ListNode* temp2 = input2 -> next;
    
29.         ListNode* temp = new ListNode(0);
    
30.         ListNode* res = temp;
    
31.         while(temp1 != NULL || temp2 != NULL){
    
32.                 if(temp1 == NULL){
    
33.                         temp -> next = temp2;
    
34.                         break;
    
35.                 }
    
36.                 if(temp2 == NULL){
    
37.                         temp -> next = temp1;
    
38.                         break;
    
39.                 }
    
40.                 if(temp1 -> value <=  temp2 -> value){
    
41.                         temp -> next = temp1;
    
42.                         temp = temp -> next;
    
43.                         temp1 = temp1 -> next;
    
44.                         continue;
    
45.                 }
    
46.                 if(temp1 -> value > temp2 -> value){
    
47.                         temp -> next = temp2;
    
48.                         temp = temp -> next;
    
49.                         temp2 = temp2 -> next;
    
50.                         continue;
    
51.                 }
    
52. 
    
53.                
    
54.         }
    
55.         return res;
    
56.        
    
57. }
    
58. 
    
59. 
    
60. int main(void){
    
61.         ListNode* input1 = new ListNode(0);
    
62.         ListNode* temp1 = input1;
    
63.         cout << "please send numbers for the first singleList:" << endl;
    
64.         int number1;
    
65.         while(cin >> number1){
    
66.                 ListNode* node = new ListNode(number1);
    
67.                 temp1 -> next = node;
    
68.                 temp1 = node;
    
69.         }
    
70.         printList(input1);
    
71.         cin.clear();
    
72.        
    
73.         ListNode* input2 = new ListNode(0);
    
74.         ListNode* temp2 = input2;
    
75.         cout << "please send numbers for the second singleList:" << endl;
    
76.         int number2;
    
77.         while(cin >> number2){
    
78.                 ListNode* node = new ListNode(number2);
    
79.                 temp2 -> next = node;
    
80.                 temp2 = node;
    
81.         }
    
82.         printList(input2);
    
83.         cin.clear();
    
84.         cout << "start!" << endl;
    
85.        
    
86.        
    
87.         ListNode* res = solution(input1, input2);
    
88.         cout << "finish!" << endl;
    
89.         printList(res);
    
90.        
    
91.        
    
92.         return 0;
    
93. }

复制代码