2023-07-31每日一题

一、题目编号

143. 重排链表

二、题目链接

点击跳转到题目位置

三、题目描述

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

	L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

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

示例 1：

示例 2：

提示：

• 链表的长度范围为 [1, 5 * 10⁴]
• 1 <= node.val <= 1000

四、解题代码

/*** 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 {ListNode* middleNode(ListNode* head){ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* fast = dummyHead;ListNode* slow = dummyHead;while(fast->next != nullptr){fast = fast->next;slow = slow->next;if(fast->next != nullptr){fast = fast->next;}}return slow;}void reverseListNode(ListNode* head1, ListNode* tail){ListNode* p = head1->next;tail = p;while(p != nullptr){ListNode* q = p;p = p->next;if(q == tail){tail->next = nullptr;continue;}head1->next = q;q->next = tail;tail = q;}}
public:void reorderList(ListNode* head) {ListNode* mid = middleNode(head);reverseListNode(mid, mid->next);ListNode* head1 = head;ListNode* head2 = mid->next;while(head1 != nullptr && head2 != nullptr){if(head1 == mid){head1->next = nullptr;}ListNode*p = head1;head1 = head1->next;if(head1 == mid){head1->next = nullptr;}p->next = head2;ListNode*q = head2;head2 = head2->next;q->next = head1;}}
};

五、解题思路

(1) 使用分治的思路来解决问题。