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

糖逗

题目描述：

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：

0 <= 链表长度 <= 1000

#include <iostream>


using namespace std;

struct ListNode{
        int value;
        ListNode* next;
        ListNode(int x): value(x), next(NULL){
                
        }
};

void printList(ListNode* input){
        ListNode* temp = input;
        while(temp -> next){
                temp = temp -> next;
                cout << temp -> value << " ";        
        }
        cout << endl;
        cout << "-------------" << endl;
        
}


ListNode* solution(ListNode* input1, ListNode* input2){
        ListNode* temp1 = input1 -> next;
        ListNode* temp2 = input2 -> next;
        ListNode* temp = new ListNode(0);
        ListNode* res = temp;
        while(temp1 != NULL || temp2 != NULL){
                if(temp1 == NULL){
                        temp -> next = temp2;
                        break;
                }
                if(temp2 == NULL){
                        temp -> next = temp1;
                        break;
                }
                if(temp1 -> value <=  temp2 -> value){
                        temp -> next = temp1;
                        temp = temp -> next;
                        temp1 = temp1 -> next;
                        continue;
                }
                if(temp1 -> value > temp2 -> value){
                        temp -> next = temp2;
                        temp = temp -> next;
                        temp2 = temp2 -> next;
                        continue;
                }

                
        }
        return res;
        
}


int main(void){
        ListNode* input1 = new ListNode(0);
        ListNode* temp1 = input1;
        cout << "please send numbers for the first singleList:" << endl;
        int number1;
        while(cin >> number1){
                ListNode* node = new ListNode(number1);
                temp1 -> next = node;
                temp1 = node;
        }
        printList(input1);
        cin.clear();
        
        ListNode* input2 = new ListNode(0);
        ListNode* temp2 = input2;
        cout << "please send numbers for the second singleList:" << endl;
        int number2;
        while(cin >> number2){
                ListNode* node = new ListNode(number2);
                temp2 -> next = node;
                temp2 = node;
        }
        printList(input2);
        cin.clear();
        cout << "start!" << endl;
        
        
        ListNode* res = solution(input1, input2);
        cout << "finish!" << endl;
        printList(res);
        
        
        return 0;
}