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

给定一个单链表 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;
    }
}
THE END