解题思路

本题采用双指针解法。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        if(pHead1==nullptr) return pHead2;
        if(pHead2==nullptr) return pHead1;
        if(pHead1->val > pHead2->val){
            int temp = pHead2->val;
            pHead2->val = pHead1->val;
            pHead1->val = temp;
        }
        ListNode* pre = pHead1;
        ListNode* temp1 = pHead1 -> next;
        ListNode* temp2 = pHead2;
        ListNode* ans = pHead1;
        while(1){
            if(temp1==nullptr){
                pre->next = temp2;
                break;
            }
            if(temp2==nullptr) break;
            if(temp1->val >= temp2->val){
                pre->next = temp2;
                temp2 = temp2->next;
                pre->next->next = temp1;
                pre = pre->next;
            }
            else{
                pre = pre->next;
                temp1 = temp1->next;
            }
        }
        return ans;
    }
};

时间复杂度：O(M+N)。其中M, N分别为两链表的长度。

空间复杂度：O(1)。