Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
/**
* 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) {
ListNode *p, *q;
p = head, q = head;
if (head == NULL||head->next==NULL||head->next->next==NULL) return;
//find the mid
while (q&&q->next&&q->next->next){
q = q->next->next;
p = p->next;
}
q=p->next;
p->next=NULL;
reverseList(q);
mergeList(head, q);
}
void reverseList(ListNode *&head) {
ListNode *p, *q;
p = head, q =NULL;
if (head == NULL) return;
while (p->next){
q = p->next;
p->next = q->next;
q->next = head;
head = q;
}
}
void mergeList(ListNode *list_1, ListNode *list_2) {
ListNode *p, *q,*tmp;
p = list_1, q = list_2;
while (q){
tmp = q->next;
q->next = p->next;
p->next = q;
p = q->next;
q = tmp;
}
}
};