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) {            LinkedList
     
       list = new LinkedList<>();            ListNode temp=head;    //        list.addLast(temp);            boolean flag=false;            while (temp.next!=null) {                list.addLast(temp.next);                temp=temp.next;            }            temp=head;            while (!list.isEmpty()) {                if (flag) {                    temp.next=list.pollFirst();                    flag=false;                }else {                    temp.next=list.pollLast();                    flag=true;                }                temp=temp.next;            }            temp.next=null;                    }    }}