给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.解题思路：常规解法是遍历ListNode保存在list里面，然后通过list.get（i）来获取到后半段的ListNode来插入到原链表中。也可以用快慢指针找到链表的中点，然后翻转后半段的链表，然后前半段和后半段链表依次插入。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null) return ; ListNode node = head.next; ListNode root = head; //快慢指针找中位点 while (node != null && node.next!= null){ root = root.next; node = node.next.next; } // System.out.println(1); ListNode fanNode = help(root.next); // System.out.println(2); root.next = null; insertNode(head,fanNode); } //两段链表插入 private void insertNode(ListNode head, ListNode fanNode) { ListNode hnode ; ListNode fnode ; while(head!= null && fanNode != null){ hnode = head.next; fnode =fanNode.next; head.next = fanNode; fanNode.next = hnode; head = hnode; fanNode = fnode; } } //翻转后半段链表 private ListNode help(ListNode next) { if(next == null || next.next == null) return next; ListNode node = next.next; next.next = null; while( node.next != null){ ListNode chnode = node.next; node.next = next; next = node; node = chnode; } node.next = next; return node; } }
