题目：http://www.lintcode.com/zh-cn/problem/reorder-list/
给定一个单链表L: L0→L1→…→Ln-1→Ln,
重新排列后为：L0→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
一.目的：将一个链表不断的头尾链接二.思路：
第一步，先将整个链表分为前后两部分，用快慢指针的方法查找中点；
第二步，将后面的部分翻转；
第三部，创建一个新的node，将两个链表归并入这个新的链表
三.易错点：
1.翻转后半部分时候，传入的数据应该为mid的后一个，且fast在定义的时候应该为slow的下一个而不是同一起点；
2.翻转之后mid节点后面应该加一个null节点；
3.快慢节点找中点时候判断是否结束语句应该先 fast 后fast.next，因为如果当fast 指向空时，此时无 next 这时候先判断next 程序会报错
该题代码如下：
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The head of linked list. * @return: void */ public void reorderList(ListNode head) { if(head == null || head.next == null){ return; } ListNode mid = findMid(head); ListNode tail = reverse(mid.next); //不是传入mid mid.next = null; //易忘记 merge(head,tail); } private ListNode reverse(ListNode head){ ListNode newhead = null; while(head != null){ ListNode temp = head.next; head.next = newhead; newhead = head; head = temp; } return newhead; } private ListNode findMid(ListNode head){ ListNode slow = head , fast = head.next; while(fast != null && fast.next != null){ //先fast后fast.next 否则将会出错 如2-1-0-null //while(fast.next != null && fast != null){ fast = fast.next.next; slow = slow.next; } return slow; } private void merge(ListNode node1,ListNode node2){ int index = 0; ListNode dummy = new ListNode(0); while(node1 != null && node2 != null){ if(index % 2 ==0){ dummy.next = node1; node1 = node1.next; }else{ dummy.next = node2; node2 = node2.next; } index++; dummy = dummy.next; } if(node1 == null){ dummy.next = node2; }else{ dummy.next = node1; } } }
