[数据结构与算法]NC2重排链表

示例1

输入：
{1,2,3,4}
返回值：
{1,4,2,3}
说明：
给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1

示例2

输入：
{1,2,3,4,5}
返回值：
{1,5,2,4,3}
说明：
给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出    

由于链表不能直接像数组那样直接访问，每次访问一个数据都要从头访问，比较耗时。
方法1：线性表：ArrayList底层是用数组实现的，可以把链表里的节点全部放入ArrayList中，并使用两个指针把节点串起来。

public void reorderList(ListNode head){
	if(head == null)return;
	ArrayList<ListNode> arrayList=new ArrayList<>();
	//把链表中的节点录入ArrayList
	while(head.next != null){
	arrayList.add(head);
	}
	//定义两个指针
	int i=0,j=arrayList.size()-1;
	//将节点串起来
	while(i>j){
	if(i==j)return;
	arrayList.get(i).next=arrayList.get(j); 
	i++;
	arrayList.get(j).next=arrayList.get(i);
	j++;
	}
	//把最后一个节点指向null
	arrayList.get(i).next=null;
}

方法2：转换为两个链表