Leetcode 3.12

leetcode hot 100

- 链表
- - 1.两两交换链表中的节点
  - 2.随机链表的复制
  - 3.排序链表

链表

1.两两交换链表中的节点

两两交换链表中的节点

在这里插入图片描述

1.必须要设置一个dummy (temp) 结点
2.保存第二个节点
3.先让第一个节点指向第三个节点
4.再让第二个节点指向第一个节点
5.最后让dummy指向第二个节点
6.更新dummy节点，和当前节点
7.尝试了以下，以上交换的步骤3-5可以任意修改顺序

/**
 * 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* swapPairs(ListNode* head) {
        ListNode* p = head;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* ans = dummy;
        int i = 0;
        while (p != nullptr && p->next != nullptr) {
            //保存第二个节点
            auto tmp = p->next;
            //第一个节点指向第三个节点
            p->next = tmp->next;
            //第二个节点指向第一个节点
            tmp->next = p;
            //dummy指向第二个节点
            dummy->next = tmp;
            //更新指针
            dummy = p;
            p = p->next;
        }
        return ans->next;
    }
};

2.随机链表的复制

随机链表的复制

两个循环
先用一个循环，用unordered_map把两个链表捆绑
再用一个循环构建新链表的引用指向
- 建立新的next和random指向
  - mp[q]->next = mp[q->next]
  - mp[q]->random = mp[q->random]
- 遍历至原链表下一节点
mp[head] 就是新链表的头节点

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> mp;
        Node* p = head;
        //绑定链表
        while (p != nullptr) {
            mp[p] = new Node(p->val);
            p = p->next;
        }
        Node* q = head;
        //建立新的引用指向
        while (q != nullptr) {
            mp[q]->next = mp[q->next];
            mp[q]->random = mp[q->random];
            q = q->next;
        }
        return mp[head];
    }
};

3.排序链表

排序链表
放入vector，排序后覆盖原数组……开个玩笑，来看官解吧：

找到链表中点。
- 快指针 = head->next, 慢指针 = slow->next
- 快指针走两步，慢指针走一步，快指针到末尾时慢指针为链表中点
- 找到中点 slow 后，执行 slow.next = nullptr 将链表切断
- 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp (因为链表是从 slow 切断的)。
- cut 递归终止条件：当 head.next == nullptr 时，说明只有一个节点了，直接返回此节点。
将两个子链表排序合并，这里可以用到合并两个有序链表
- 双指针法合并，建立辅助 ListNode* dummy 作为头部。
- 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
返回辅助ListNode dummy作为头部的下个节点 h.next。

时间复杂度：O(nlog⁡n)，其中 n 是链表的长度。

空间复杂度：O(log⁡n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

在这里插入图片描述

/**
 * 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* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode* fast = head->next, *slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* tmp = slow->next;
        slow->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(tmp);
        ListNode* dummy = new ListNode(0);
        ListNode* ans = dummy;
        while (left != nullptr && right != nullptr) {
            if (left->val > right->val) {
                ans->next = right;
                right = right->next;
            } else {
                ans->next = left;
                left = left->next;
            }
            ans = ans->next;
        }
        ans->next = left == nullptr ? right : left;
        return dummy->next;
    }
};