算法日常・每日刷题--＜链表＞3

LCR 026. 重排链表 - 力扣LeetCodeLCR 026. 重排链表 - 给定一个单链表 L 的头节点 head 单链表 L 表示为 L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …不能只是单纯的改变节点内部的值而是需要实际的进行节点交换。 示例 1[https://pic.leetcode.cn/1626420311-PkUiGI-image.png]输入: head [1,2,3,4]输出: [1,4,2,3]示例 2[https://pic.leetcode.cn/1626420320-YUiulT-image.png]输入: head [1,2,3,4,5]输出: [1,5,2,4,3] 提示 * 链表的长度范围为 [1, 5 * 104] * 1 node.val 1000 注意本题与主站 143 题相同https://leetcode.cn/problems/reorder-list/ [https://leetcode.cn/problems/reorder-list/]https://leetcode.cn/problems/LGjMqU/description/题目描述给定单链表头节点head原始链表限制不能修改节点内数值必须调整节点指针。示例 输入链表1 → 2 → 3 → 4输出链表1 → 4 → 2 → 3解法快慢指针找到链表中点快指针一次走 2 步慢指针一次走 1 步循环结束后慢指针指向链表中点。 把链表切分成前后两半 前半段L0 → L1 → …后半段Lmid → … → Ln反转后半段链表后半段反转之后顺序变为Ln → Ln-1 → … → Lmid交替合并两个链表依次从前半段、反转后的后半段取节点拼接完成重排。/** * 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: void reorderList(ListNode* head) { if(!head || !head-next) return; // 1.快慢指针找中点 ListNode *slow head, *fast head; while(fast-next fast-next-next){ slow slow-next; fast fast-next-next; } // 分割前后两段 ListNode* mid slow-next; slow-next nullptr; // 2.反转后半段链表 ListNode* prev nullptr; ListNode* cur mid; while(cur){ ListNode* nxt cur-next; cur-next prev; prev cur; cur nxt; } ListNode* rHalf prev; // 反转后的后半段头节点 // 3.交替合并两个链表 ListNode* p1 head; ListNode* p2 rHalf; while(p2){ ListNode* n1 p1-next; ListNode* n2 p2-next; p1-next p2; p2-next n1; p1 n1; p2 n2; } } };