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. * class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public void reorderList(ListNode head) {        if(head != null){            ListNode stepOne = head, stepTwo = head;            while(stepTwo.next != null){                if(stepTwo.next != null)                    stepTwo = stepTwo.next;                if(stepTwo.next != null){                    stepTwo = stepTwo.next;                    stepOne = stepOne.next;                }            }            if(stepOne.next != null){                stepTwo = stepOne.next;                stepOne.next = null;                ListNode tailOfSecond = stepTwo;                stepOne = stepTwo;                if(stepTwo.next != null)                    stepTwo = stepTwo.next;                while(stepTwo.next != null){                    ListNode temp = stepTwo.next;                    stepTwo.next = stepOne;                    stepOne = stepTwo;                    stepTwo = temp;                }                stepTwo.next = stepOne;                tailOfSecond.next = null;            }            stepOne = head;            if(stepTwo != stepOne){                while(stepTwo != null){                    ListNode temp = stepOne.next;                    stepOne.next = stepTwo;                    stepOne = stepOne.next;                    stepTwo = temp;                }            }        }            }}