题目

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

思路

建头、尾新指针。两个链表，链表头结点值，尾指针指向较小值的结点，然后此链表头指针后移一位，直至有一个链表结束。返回新指针。

示例

list1：0 1 2 3 4 5 6 7 list2：3 4 5 6 7 8 9 10 11 12 13 合并后：0 1 2 3 3 3 4 4 5 5 6 6 7 7 8 9 10 11 12 13

代码

#include <iostream> using namespace std; struct ListNode { int val; ListNode * next; ListNode(int x): val(x),next(nullptr){ } }; class Solution{ public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2){ ListNode* nHead(nullptr),*tail(nullptr); if(pHead1 == nullptr) return pHead2; if(pHead2 == nullptr) return pHead1; if(pHead1 -> val < pHead2 -> val){ nHead = tail = pHead1; pHead1 = pHead1 -> next; } else{ nHead = tail = pHead2; pHead2 = pHead2 -> next; } while (pHead1 && pHead2 ){ if(pHead1 -> val < pHead2 -> val){ tail -> next = pHead1; tail = tail -> next; pHead1 = pHead1 ->next; } else{ tail -> next = pHead2; tail = tail -> next; pHead2 = pHead2 -> next; } } if(pHead1 == nullptr) tail -> next = pHead2; else if(pHead2 == nullptr) tail -> next = pHead1; return nHead; } }; int main(){ Solution re; struct ListNode* head,*list1,*list2,*head2; struct ListNode node(0),node1(3); list1 = head = &node; for (int i = 1; i < 8; ++i) { struct ListNode *p = new ListNode(i); head -> next = p; head = head -> next; } head2 = list2 = &node1; for (int j = 3; j < 14 ; ++j) { struct ListNode *p = new ListNode(j); head2 -> next = p; head2 = head2 ->next; } // /* struct ListNode *result = re.Merge(list1,list2); while (result){ // cout << "2111111" << endl; cout << result -> val << " "; result = result -> next; } //*/ return 0; }