## Reorder List

Given a singly linked list

L:L_{0}→L_{1}→…→L_{n-1}→L_{n},

reorder it to:L_{0}→L_{n}→L_{1}→L_{n-1}→L_{2}→L_{n-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}`

.

The algorithm is straightforward.

First, divide the linked list into two parts equally. (left part may be longer than right part by one node)

Second, reverse the right part list.

Third, link the two parts craftily.

//What if the list is empty? //What if the list contains odd elements? //What time complexity? //space complexity o(1) //1. split the list into two parts //2. reverse the right part list //3. link them together /** * 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) { //extreme cases if(head == NULL) return ; //ordinary cases //1. find the mid of the list ListNode * fast, * slow; fast = slow = head; while(fast->next != NULL && fast->next->next != NULL){ fast = fast->next->next; slow = slow->next; } ListNode * leftStart = head; ListNode * rightStart = slow->next; // rightStart may be NULL slow->next = NULL; rightStart = reverse(rightStart); //list left may be longer than right by one node while(rightStart != NULL){ ListNode * leftNext = leftStart->next; ListNode * rightNext = rightStart->next; leftStart->next = rightStart; rightStart->next = leftNext; leftStart = leftNext; rightStart = rightNext; } } //o(n), reverse linked list ListNode * reverse(ListNode * head){ if(head == NULL) return NULL; ListNode * prev, * cur, * next; prev = NULL; cur = head; while(cur != NULL){ next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; } };