首页 > 代码库 > Problem Reorder List

Problem Reorder List

Problem Description:

Given a singly linked list LL0→L1→…→Ln-1→Ln,

reorder it to: L0→LnL1→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}.

 

Solution: 
 1 public void reorderList(ListNode head) { 2         int length = 0; 3         ListNode p = head; 4         List<ListNode> list = new ArrayList<ListNode>(); 5         while (p != null) { 6             length++; 7             list.add(p); 8             p = p.next; 9         }10         int i = 0;11         p = null;12         while (i <= (length - 1 - i)) {13             if (p != null) {14                 p.next = list.get(i);15             }16             if (i != length -1 -i) {17                 list.get(i).next = list.get(length - 1-i);18                 p = list.get(length-1-i);19                 p.next = null;20             } else {21                 list.get(i).next = null;22             }23 24             i++;25         }26     }