题目：
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}. 基本思路： 用了一个很蠢很直接的方法，定位到中间节点，后半段入栈，然后把后半段与前半段拼接组成新链表
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public void reorderList(ListNode head) { 11 12 13 if (head == null) 14 return; 15 16 ListNode node = head.next; 17 int len = 0; 18 while(node != null){ 19 len ++; 20 node = node.next; 21 } 22 23 System.out.println("len:"+len); 24 25 if(len == 2){ 26 ListNode temp = head.next; 27 28 head.next = temp.next; 29 temp.next = null; 30 head.next.next = temp; 31 return; 32 }else if(len == 1 || len == 0){ 33 return; 34 } 35 36 int isOdd = len % 2; 37 if(isOdd == 1){ 38 int mid = len / 2 + 1; 39 Stack stack = new Stack(); 40 41 int j = 1; 42 ListNode midNode = head.next; 43 while(j != mid){ 44 j++; 45 midNode = midNode.next; 46 } 47 48 ListNode realMidNode = midNode; 49 midNode = midNode.next; 50 j++; 51 stack.push(midNode); 52 while(j != len){ 53 j++; 54 midNode = midNode.next; 55 stack.push(midNode); 56 } 57 58 j = 1; 59 60 ListNode leftTemp = head.next; 61 ListNode rightTemp = stack.pop(); 62 rightTemp.next = leftTemp; 63 head.next = rightTemp; 64 ListNode tail = leftTemp; 65 j++; 66 while(j < mid){ 67 j++; 68 leftTemp = leftTemp.next; 69 rightTemp = stack.pop(); 70 rightTemp.next = leftTemp; 71 tail.next = rightTemp; 72 tail = leftTemp; 73 } 74 75 tail.next = realMidNode; 76 realMidNode.next = null; 77 78 }else{ 79 int mid = len / 2 ; 80 Stack stack = new Stack<>(); 81 82 int j = 1; 83 ListNode midNode = head.next; 84 while(j != mid){ 85 j++; 86 midNode = midNode.next; 87 } 88 89 j++; 90 midNode = midNode.next; 91 stack.push(midNode); 92 93 while(j != len){ 94 j++; 95 midNode = midNode.next; 96 stack.push(midNode); 97 } 98 99 100 101 j=1;102 103 ListNode leftTemp = head.next;104 ListNode rightTemp = stack.pop();105 rightTemp.next = leftTemp;106 head.next = rightTemp;107 ListNode tail = leftTemp; 108 109 while(j != mid){110 j++;111 leftTemp = leftTemp.next;112 rightTemp = stack.pop();113 rightTemp.next = leftTemp;114 tail.next = rightTemp;115 tail = leftTemp;116 }117 tail.next = null;118 }119 120 }121 } 运行结果
