/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (head == NULL || head->next == NULL)
return;
ListNode* mid = searchHalf(head);
reverseHalf(mid);
merge(head, mid);
}
private:
// 快速找到中点
ListNode* searchHalf(ListNode* head){
ListNode *slowPtr = head, // 同时起跑
*fastPtr = head; // 当快的跑完length，慢的正好跑了（length + 1）/ 2
while(fastPtr->next && fastPtr->next->next){
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
}
return slowPtr;
}
// 链表的逆置
void reverseHalf(ListNode* head){
ListNode* tmp =head->next;
head->next = NULL; // 先清空头结点
for (ListNode* ptr = tmp; ptr;){
ListNode* tmp = ptr->next;
ptr->next = head->next;
head->next= ptr;
ptr = tmp;
}
}
void merge(ListNode* left, ListNode* right){
ListNode* tmp = right->next;
right->next =NULL;
right =tmp;
while (left && right){
ListNode* helper_left = left->next;
ListNode* helper_right = right->next;
right->next = left->next;
left->next = right;
right = helper_right;
left = helper_left;
}
}
};
转载请注明原文地址: https://ju.6miu.com/read-1310022.html
