LeetCode-21. 合并两个有序链表

题目

21.合并两个有序链表

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *p = list1, *q = list2, *newList, *curr;
        newList = new ListNode(0);
        curr = newList;
        while(p && q) {
            if(p->val < q->val) {
                curr->next = p;
                curr = curr->next;
                p = p->next;
            } else {
                curr->next = q;
                curr = curr->next;
                q = q->next;
            }
        }
        if(p) {
            curr->next = p;
            p = p->next;
            curr = curr->next;
        }
        if(q) {
            curr->next = q;
            q = q->next;
            curr = curr->next;
        }
        return newList->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *newHead, *p0, *p1, *p2;
        newHead = new ListNode(0);
        p0 = newHead;
        p1 = list1;
        p2 = list2;
        while(p1 && p2) {
            if(p1->val < p2->val) {
                p0->next = p1;
                p1 = p1->next;
            } else {
                p0->next = p2;
                p2 = p2->next;
            }
            p0 = p0->next;
        }
        p0->next = p1 == nullptr ? p2 : p1;
        return newHead->next;
    }
};

思路一

思路一与合并两个有序数组的思路一样，定义一个新链表，比较已给两个链表的值，双指针，小的插到新链表去

思路二

直接改变链表节点的指向，不需要额外内存

如果p1当前节点的值小于等于p2，就把p1当前的节点接在p0节点的后面同时将p1指针往后移一位；反之

这里要注意的是，当p1或p2为NULL时，剩下还需要连接一个节点，所以直接写p0->next = p1 == nullptr ? p2 : p1;

复杂度

思路一：时间复杂度O(n+m)，空间复杂度O(n+m)

思路二：时间复杂度O(n+m)，空间复杂度O(1)