Leetcode: 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 must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Hide Tags

 Linked List

-----------------------------------------------------------------

As the pointer of list can't move backward, double pointers method scan from two end to the center doesn't work. So we need to think about way to do it with an forward direction. Following is one of such method:

1. locate the middle of the list: 

    there are two kinds, odd and even number of nodes, the middle one should be calculated differently. 

2. reverse the order for all the nodes in right side of middle node. For how to reverse the whole linked list, check there. 

3. merge the list with forward order. 

when number of node is even, the procedure is shown below:

when number of node is odd, the procedure is shown as:

////////////////////////////////////////////////

////code

class Solution {

public:

       void reorderList(ListNode* head) {

              //check input

              if (head == NULL || head->next == NULL || head->next->next == NULL) return;

              //find the middle and final location

              int len = 1, midLen = 0;

              ListNode *mid = head, *final = head, *tmp = head, *left = head;

              while (mid->next != NULL) { len++; mid = mid->next; }

              final = mid;

              mid = head;

              //locate the mid

              midLen = (len % 2) == 1 ? len / 2 + 1 : len / 2;

              for (int i = 1; i<midLen; i++){

                     mid = mid->next;

              }

              tmp = mid;

              //reverse the right half list

              ListNode* cur = tmp->next;

              ListNode* pre = cur->next;

              cur->next = NULL;//the final node after reverse

              while (pre != NULL)

              {

                     ListNode* temp = pre->next;

                     pre->next = cur;

                     cur = pre;

                     pre = temp;

              }

              tmp->next = cur;

              //reorder the list

              mid = tmp;

              for (int i = 1; i <= len - midLen; i++){

                     tmp = left->next;

                     left->next = mid->next;

                     mid->next = mid->next->next;

                     left->next->next = tmp;

                     //update pointers

                     left = left->next->next;

                     if (left == mid)break;

              }

              return;

       }

};