首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >单双向链表反转【面试题】

单双向链表反转【面试题】

作者头像
田维常
发布2019-08-21 18:01:27
1.6K0
发布2019-08-21 18:01:27
举报

题目

实现反转单向链表和双向链表,要求:如果链表长度为N,时间复杂度为O(N),额外空间复杂度为O(1)

参考答案

图形表示

单向链表

单向反转请参考Java实现单链表及相关操作 双向链表

反转前:头节点的前驱是null,尾节点的后继是null。

反转后:以前的头节点的后继是null,以前的尾节点的前驱是null

java代码实现如下:

//双向链表节点
public class DoubleNode {
    public int value;
    //前驱
    public DoubleNode pre;
    //后继
    public DoubleNode next;

    public DoubleNode(int value) {
        this.value = value;
    }
}
public class DoubleNodeReversal {
    public static void main(String[] args) {
        DoubleNode head = new DoubleNode(1);
       //构建一个双向链表1 2 3 4
        DoubleNode mid1 = new DoubleNode(2);
        DoubleNode mid2 = new DoubleNode(3);
        DoubleNode tail = new DoubleNode(4);
        head.next = mid1;
        mid1.next = mid2;
        mid2.next = tail;

        System.out.println("反转前");
        print(head);
        head = reversalList(head);
        System.out.println("反转后");
        print(head);
    }
   //把自己的前驱变后继,把后继变前驱 
    private static DoubleNode reversalList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.pre = next;
            pre = head;
            head = next;
        }
        System.out.println();
        return pre;
    }
   //遍历打印节点信息
    private static void print(DoubleNode head) {
        while (head != null) {
            System.out.print(head.value);           //优化打印日格式
            System.out.print(" ");
            head = head.next;
        }
    }
}
关键字

链表,单向,双向,反转

老规矩,代码截图,免得手机上看代码很不爽

【文章汇总】面试篇

【文章汇总】Java基础篇

【文章汇总】性能调优篇

【文章汇总】设计模式篇

【文 章 汇 总】Spring家族篇

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-08-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Java后端技术栈 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
  • 参考答案
    • 关键字
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档