【C++刷题】优选算法——链表

链表常用技巧和操作总结

• 常用技巧
  画图
  引入虚拟头节点
  不要吝啬空间，大胆定义变量
  快慢双指针
• 常用操作
  创建一个新节点
  尾插
  头插

1. 两数相加

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {int carry = 0;ListNode* newHead = new ListNode, *cur = newHead;while (l1 != nullptr && l2 != nullptr) {int num = l1->val + l2->val + carry;carry = num / 10;num = num % 10;cur->next = new ListNode(num);cur = cur->next;l1 = l1->next;l2 = l2->next;}while (l1 != nullptr) {int num = l1->val + carry;carry = num / 10;num = num % 10;cur->next = new ListNode(num);cur = cur->next;l1 = l1->next;}while (l2 != nullptr) {int num = l2->val + carry;carry = num / 10;num = num % 10;cur->next = new ListNode(num);cur = cur->next;l2 = l2->next;}if (carry != 0) {cur->next = new ListNode(carry);}return newHead->next;
}

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

ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode *front = head, *back = front->next, *newHead = new ListNode, *cur = newHead;while (true) {cur->next = back;ListNode* tmp = back->next;back->next = front;front->next = tmp;cur = front;if (tmp != nullptr && tmp->next != nullptr) {front = tmp;back = front->next;} else if (tmp != nullptr && tmp->next == nullptr) {cur->next = tmp;return newHead->next;} else {return newHead->next;}}
}

3. 重排链表

ListNode* reverse(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* newHead = reverse(head->next);head->next->next = head;head->next = nullptr;return newHead;
}
void reorderList(ListNode* head) {ListNode *slow = head, *fast = head;while (fast != nullptr && fast->next != nullptr) {slow = slow->next;fast = fast->next->next;}ListNode* cur1 = head, *cur2 = reverse(slow);ListNode* newHead = new ListNode, *cur = newHead;while (cur1 != cur2 && cur2 != nullptr) {cur->next = cur1;cur1 = cur1->next;cur = cur->next;cur->next = cur2;cur2 = cur2->next;cur = cur->next;}
}

4. 合并 K 个升序链表

// 解法一
ListNode* mergeKLists(vector<ListNode*>& lists) {// 小根堆priority_queue<ListNode*, vector<ListNode*>, Comp> pq;for (ListNode* e : lists) {if (e != nullptr) {pq.push(e);}}ListNode *newHead = new ListNode, *cur = newHead;while (!pq.empty()) {cur->next = pq.top();cur = cur->next;pq.pop();if (cur->next != nullptr) {pq.push(cur->next);}}return newHead->next;
}// 解法二
ListNode* merge_sort(vector<ListNode*>& lists, int start, int end) {if (start > end) return nullptr;else if (start == end) return lists[start];int mid = start + (end - start) / 2;ListNode* left = merge_sort(lists, start, mid);ListNode* right = merge_sort(lists, mid + 1, end);if (left == nullptr) return right;else if (right == nullptr) return left;ListNode *newHead = new ListNode, *cur = newHead;while (left != nullptr && right != nullptr) {if (left->val < right->val) {cur->next = left;left = left->next;} else {cur->next = right;right = right->next;}cur = cur->next;}while (left != nullptr) {cur->next = left;left = left->next;cur = cur->next;}while (right != nullptr) {cur->next = right;right = right->next;cur = cur->next;}return newHead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {return merge_sort(lists, 0, lists.size() - 1);
}

5. K 个一组翻转链表

ListNode* reverseKGroup(ListNode* head, int k) {int total = 0;ListNode* cur = head;while (cur != nullptr) {++total;cur = cur->next;}ListNode* newHead = new ListNode;cur = newHead;while (head != nullptr) {int count = k;ListNode* tail = head;if (total >= k) {while (count-- && head != nullptr) {ListNode* tmp = head->next;head->next = cur->next;cur->next = head;head = tmp;}total -= k;}cur = tail;if (total < k) {cur->next = head;break;}}return newHead->next;
}