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.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) { try{
if(head.next.next!=null){
ListNode p=head; Map<ListNode,ListNode> map=new HashMap<>(); while(p.next.next!=null)
{
map.put(p.next,p);
p=p.next;
}
ListNode q=head;
ListNode temp=p.next; while(q.next!=p.next&&q.next!=null)
{
p.next=temp.next;
temp.next=q.next;
q.next=temp;
q=temp.next; temp=p;
p=map.get(p);
} } }catch(NullPointerException e){} }
}