网站原创页面厦门百度整站优化服务

题干

LCR 026. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

 L0 → L1 → … → Ln-1 → Ln 
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解法：寻找链表中点 + 链表逆序 + 合并链表

/*** 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 *getMid(ListNode* head) {ListNode* fast = head;ListNode* slow = head;while (fast != nullptr && fast->next != nullptr) {fast = fast->next->next;slow = slow->next;}return slow;}// 反转链表ListNode *revers(ListNode* head) {ListNode *pre = nullptr;ListNode *curr = head;while (curr != nullptr) {ListNode *next = curr->next;curr->next = pre;pre = curr;curr = next;}return pre;}// 合并两个链表void merge(ListNode *l1, ListNode *l2) {ListNode *l1_tmp;ListNode *l2_tmp;while (l1 != nullptr && l2 != nullptr) {l1_tmp = l1->next;l2_tmp = l2->next;l1->next = l2;l1 = l1_tmp;l2->next = l1;l2 = l2_tmp;}}// 重新排序链表void reorderList(ListNode* head) {if (head == nullptr || head->next == nullptr) {return;}ListNode* mid = getMid(head);ListNode *rightHead = mid->next;mid->next = nullptr;ListNode *reversedRight = revers(rightHead);merge(head, reversedRight);}
};

解析：

这道题综合了前几道题比较基础的算法，正好可以用来复习。

1.找到原链表的中点（参考「876. 链表的中间结点」）。
2.将原链表的右半端反转（参考「206. 反转链表」）。
3.合并两个链表。