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

2022-03-2709:27:30数据结构与算法Comments941 views字数 1329阅读模式

给定一个单链表 L 的头节点 head ,单链表 L 表示为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

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

输入:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

head = [1,2,3,4]

输出:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

[1,4,2,3]

思路:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

如果是数组就好了,哈哈,因为数组可以直接通过下标访问,很容易就可以解答这道题了。但是这是链表。链表不支持下标访问,我们没办法随机访问到链表任意位置的元素,怎么办呢?文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

我们可以先遍历一下,用数组把链表的元素按顺序存储起来呀,然后就可以把它当做数组这么访问来用了对吧,最后重建下链表即可啦。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

ArrayList的底层就是数组,我们先用它存储链表就好,如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

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

有了一个数组结构的链表后,如何重建链表呢?回头多看示例两眼,很容易就发小规律啦:先排第1个,再排倒数第1个,接着排第2个,紧接着倒数第2个。显然这个规律很明显,代码也比较好实现:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

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;

完整实现代码如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html

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;
    }
}
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23739.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/23739.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定