腾讯常考十道算法真题:重排链表
给定一个单链表 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