腾讯算法常见题：重新排列链表

给定一个单链表 L 的头节点，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

重新排列为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

输入： 输出：

[1,4,2,3]

想法：

如果是数组就太好了，哈哈，因为数组可以通过订阅者直接访问，回答这个问题很简单。但这是一个链表。 链接列表不支持订阅访问。 我们不能随机访问链表中任意位置的元素。我们应该做什么？

我们可以先遍历一下，用数组按顺序存储链表的元素，然后再以数组的形式访问，对吧？最后，重建链表。

ArrayList的底层是一个数组。我们只是先用它来存储链表，如下：

 List<ListNode> list = new ArrayList<ListNode>();
 ListNode node = head;
 while (node != null) {
    list.add(node);
    node = node.next;
}

有了数组结构的链表后如何重建链表？如果你回顾一下这些例子，你会很容易发现一个小规律：首先是第一个，然后是从底部开始的第一个，然后是第二个，然后是从底部开始的第二个。这个规则显而易见，代码也比较容易实现：

int i = 0;
int j = list.size()-1;
while(i<j){
    list.get(i).next = list.get(j);
    i++;
    if(i==j){
      break;
   }
   list.get(j).next = list.get(i);
   j--;
}
//大家画个图就很清晰知道为什么需要这行了，哈哈
 list.get(i).next = null;

完整的实现代码如下：

class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        List<ListNode> list = new ArrayList<ListNode>();
        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        int i = 0, j = list.size() - 1;
        while (i < j) {
            list.get(i).next = list.get(j);
            i++;
            if (i == j) {
                break;
            }
            list.get(j).next = list.get(i);
            j--;
        }
        list.get(i).next = null;
    }
}