专业设计网站排行榜_深圳坪山人民医院_制作网站的基本步骤_福州关键词搜索排名

一、示例

二、上代码

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，采用了快慢指针的算法。

2、链表逆序参考前面文章：链表逆序
本文采用的正向遍历，前面文章采用的递归，都要掌握。

3、合并前半段链表和后半段链表。