LeetCode 21. 合并两个有序链表

 这题单从思想上来说，和归并排序差不多，使用两个指针分别指向两个链表的开头，比较大小，将较小的插入到新的链表中。在其中一个链表循环完成后，将另一个链表的剩余部分接上即可。AC代码如下：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* left = list1;
        ListNode* right = list2;
        ListNode* ans = new ListNode;
        ListNode* tail = ans; 
        for(;left!=nullptr&&right!=nullptr;) {
            if((left->val) <= (right->val)) {
                tail->next = left;
                left = left->next;
            }else {
                tail->next = right;
                right = right->next;
            }
            tail = tail->next;
        }
        for(;left!=nullptr;left=left->next) {
            tail->next = left;
            tail = tail->next;
        }
        for(;right!=nullptr;right=right->next) {
            tail->next = right;
            tail = tail->next;
        }
        return ans->next;
    }
};