LeetCode [143] 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/** * 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 || !head->next || !head->next->next) return; ListNode *p1 = head, *p2 = head; while(p2 && p2->next && p2->next->next){ p1 = p1->next; p2 = p2->next->next; } ListNode *head2 = p1->next; p1->next = NULL; p2 = head2->next; head2->next = NULL; while(p2){ ListNode *next = p2->next; p2->next = head2; head2 = p2; p2 = next; } p1 = head; p2 = head2; while(p1 && p2){ ListNode *next1 = p1->next; ListNode *next2 = p2->next; p1->next = p2; p2->next = next1; p1 = next1; p2 = next2; } } };