腾讯常考十道算法真题：重排链表

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

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

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

输入：

head = [1,2,3,4]

输出：

[1,4,2,3]

思路：

如果是数组就好了，哈哈，因为数组可以直接通过下标访问，很容易就可以解答这道题了。但是这是链表。链表不支持下标访问，我们没办法随机访问到链表任意位置的元素，怎么办呢？

我们可以先遍历一下，用数组把链表的元素按顺序存储起来呀，然后就可以把它当做数组这么访问来用了对吧，最后重建下链表即可啦。

ArrayList的底层就是数组，我们先用它存储链表就好，如下：

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

有了一个数组结构的链表后，如何重建链表呢？回头多看示例两眼，很容易就发小规律啦：先排第1个，再排倒数第1个，接着排第2个，紧接着倒数第2个。显然这个规律很明显，代码也比较好实现：

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;
    }
}