LeetCode刷题实战143： 重排链表
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
题意
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
解题
首先找到链表的中间位置，从其后面拆开分成两半，保存要反向插入的后半部分的首节点，并把前半部分的最后一个节点的next指针置为NULL
然后将后半部分链表反转，并保存反转后新链表的首节点
最后从反转后的链表首节点开始，依次间隔一个位置插入到前半部分链表中
/**
* 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 *left = head, *right = head;
while(right){
right = right->next;
if(right){
right = right->next;
left = left->next;
}
}
right = left->next;
left->next = NULL;
left = NULL;
ListNode *now = right;
while(now){
right = now->next;
now->next = left;
left = now;
now = right;
}
now = head;
while(left){
right = left->next;
left->next = now->next;
now->next = left;
now = left->next;
left = right;
}
}
};