Reorder List
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.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
/**
* 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 == NULL) return;
ListNode *cur1, *cur2, *prev, *next1, *next2;
int n = 0;
cur1 = head;
while (cur1) {
n++;
cur1 = cur1->next;
}
n = n/2;
cur1 = head;
for (int i = 0; i < n; i++) {
prev = cur1;
cur1 = cur1->next;
}
next1 = cur1->next;
cur1->next = NULL;
cur1 = next1;
prev = NULL;
while (cur1) {
next1 = cur1->next;
cur1->next = prev;
prev = cur1;
cur1 = next1;
}
cur1 = head;
cur2 = prev;
while (cur1 && cur2) {
next1 = cur1->next;
cur1->next = cur2;
next2 = cur2->next;
cur2->next = next1;
cur1 = next1;
cur2 = next2;
}
return;
}
};
