Leetcode 3.12

链表

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;}
};