一、示例
二、上代码
class Solution {
public:void reorderList(ListNode* head) {if (head == nullptr || head->next == nullptr) return;ListNode* mid = FindMiddleNode(head); // 找到中间节点ListNode* l1 = head;ListNode* l2 = mid->next;mid->next = nullptr;l2 = ReverseList(l2); // 反转后半段的链表节点mergeList(l1, l2); // 合并两端长度相差不超过1的链表}// 快慢指针找到中间节点ListNode* FindMiddleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast->next != nullptr && fast->next->next != nullptr) {slow = slow->next;fast = fast->next->next;}return slow;}// 反转链表ListNode* ReverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* cur = head;ListNode* next;while (cur != nullptr) {next = cur->next;cur->next = pre; // 反转pre = cur; // 向后移动cur = next;}return pre;}// 合并链表void mergeList(ListNode* l1, ListNode* l2) {ListNode* temp1;ListNode* temp2;while (l1 != nullptr && l2 != nullptr) {temp1 = l1->next;temp2 = l2->next;l1->next = l2;l1 = temp1;l2->next = l1;l2 = temp2;}}
};
三、详解
算法思想:将链表分成两半来处理,前半部分,和后半部分;针对后半部分进行逆序,再从前半部分和逆序后的后半部分分别取一个结点组成一个新的链表。然后就将上面问题分解成更细粒度的子问题:
1、寻找中间节点 FindMiddleNode
,采用了快慢指针的算法。