[Lc]21合并两个有序链表

题目

链表定义：

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

题解

这道题的思想是链表归并排序中的一个重要环节，即对有序的两个链表进行归并。比较表头，小的接上去

• 时间复杂度$O(n)$
• 空间复杂度$O(1)$

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //核心就是挨个比较两个链表当前的数
        ListNode *DummyHead = new ListNode(-1);//设置一个哑节点
        ListNode *cur = DummyHead;//设置一个指针用于指向当前链表中的值，先指向哑节点
        while(l1 && l2){//当l1或l2均未到头时
            if(l1->val > l2->val){//哪个小就指向哪个
                cur->next = l2;
                l2 = l2->next;//再把l2指向的值往后移一位
            }
            else{
                cur->next = l1;
                l1 = l1->next;//同上
            }
            cur = cur->next;//赋值链接完毕再把cur指针往后移一位
        }
        cur->next = l1? l1:l2;//肯定有一条链表先遍历完，直接把另一条链表接到后面
        return DummyHead->next;//返回哑节点后面的值
    }
};