继续学算法~

合并链表

合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

可以准备一个假的头节点作为合成后链表的头节点，然后像归并排序那样合并有序链表，如果其中一个链表合并完/空了，直接把另一个链表的剩余节点归并。

参考代码如下：

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* head = new ListNode(-1);
    ListNode* cur = head;
    ListNode* cur1 = list1;
    ListNode* cur2 = list2;

    while (cur1 && cur2)
    {
        if (cur1->val < cur2->val)
        {
            cur->next = cur1;
            cur1 = cur1->next;
        }
        else
        {
            cur->next = cur2;
            cur2 = cur2->next;
        }
        cur = cur->next;
    }

    if (cur1)
        cur->next = cur1;
    else if (cur2)
        cur->next = cur2;

    return head->next;
}

合并k个有序链表

23. 合并 K 个升序链表 - 力扣（LeetCode）

和之前合并两个有序链表类似，但这次链表数量最多高达10^4，如果用暴力循环必定超时。因此可以使用优先队列，存储k个链表的头节点，然后将优先队列队头取出来（别忘了将它的下一个元素入队），加入假头节点链表即可。

算法时间复杂度为，其中k是链表条数，N是链表节点总数。

代码如下：

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto cmp = [](ListNode* v1, ListNode* v2){
        return v1->val > v2->val;
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q;

    // 初始化优先队列
    for (ListNode* node : lists)
        if (node)
            q.push(node);

    // 开始合并链表
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    while (!q.empty())
    {
        ListNode* node = q.top();
        q.pop();
        if (node->next)
            q.push(node->next);

        cur->next = node;
        cur = cur->next;
    }

    return dummy->next;
}

链表倒数第k个节点

单链表的倒数第k个节点

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

删除链表的倒数第k个节点，也就是删除链表正数第n-k+1个节点。可以用双指针的方式通过一次遍历得到链表的第X个节点：首先让前驱指针向前走k步，然后让前驱和后继指针同时往前走，直到前驱为空，这样后继指针就指向链表的倒数第k个节点了。

参考代码如下：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;

    // 找到倒数第n+1个节点
    ListNode* pre = dummy;
    ListNode* ne = dummy;
    while (n--)
        ne = ne->next;
    while (ne->next)
    {
        ne = ne->next;
        pre = pre->next;
    }

    // 删除倒数第n个节点
    pre->next = pre->next->next;
    return dummy->next;
}

单链表的中点

876. 链表的中间结点 - 力扣（LeetCode）

使用快慢指针，快指针每次走两下，慢指针每次走一下，这样当快指针走完后（碰到空节点），慢指针指向的就是中点了。

参考代码如下：

ListNode* middleNode(ListNode* head) {
    ListNode* fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

判断链表是否包含环

141. 环形链表 - 力扣（LeetCode）

可以用快慢指针解决，如果链表存在环，必然有快慢指针重合的情况（快指针超了慢指针一圈）。参考代码如下：

bool hasCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
            return true;
    }
    return false;
}

142. 环形链表 II - 力扣（LeetCode）

这是上面问题的进阶，需要找到环形链表的起点。

当快慢指针相遇时，快指针比慢指针多走了k步，而这个k必定是环长度的倍数。假设相遇点距离起点m步，慢指针走到相遇点用k步，快指针走到相遇点用2k步。那么从头节点到环形链表起点，从相遇点到环形链表起点都需要k-m步。

因此把其中一个指针放到起点，然后让他们同时走1步，直到二者相遇，相遇的地方就是环形链表的起点。

参考代码如下：

ListNode *detectCycle(ListNode *head) {
    ListNode *fast = head, *slow = head;

    bool isCycle = false;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            isCycle = true;
            break;
        }

    }

    if (isCycle)
    {
        fast = head;
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
    else
        return nullptr;
}

链表相交

两链表是否相交

160. 相交链表 - 力扣（LeetCode）

如图，A链表遍历完马上遍历B，B链表遍历完马上遍历A，直到它们同时到达相交节点，而这个节点可能有内容（相交了），也有可能是nullptr（不相交）。

参考代码如下：

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pa = headA;
    ListNode *pb = headB;

    while (pa != pb)
    {
        pa = pa == nullptr ? headB : pa->next;
        pb = pb == nullptr ? headA : pb->next;
    }

    return pa;
}