前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Java数据结构-链表

Java数据结构-链表

作者头像
瑞新
发布2020-07-07 14:27:35
3500
发布2020-07-07 14:27:35
举报
文章被收录于专栏:用户3288143的专栏

Java数据结构-链表
  • 单链表
    • 简单实现
      • 输出:
      • 代码
    • 面试题
      • 1题目描述
      • 2分析
      • 3代码
    • 4.复杂度

单链表

简单实现

输出:

火车头 车厢1 车厢2

代码
代码语言:javascript
复制
public class Solution {
    private String data;
    private Solution next;

    public Solution(String data) {
        this.data = data;
    }

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Solution getNext() {
        return next;
    }

    public void setNext(Solution next) {
        this.next = next;
    }

    public static void main(String[] args) {
        //初始化链表
        Solution l0 = new Solution("火车头");
        Solution l1 = new Solution("车厢1");
        Solution l2 = new Solution("车厢2");
        //设置指针
        l0.setNext(l1);
        l1.setNext(l2);
        //读取链表数据
        Solution data = l0;
        while (data!=null){
            System.out.println(data.getData());
            data = data.getNext();
        }


    }
}

面试题

1题目描述

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

2分析

listNode 是链表,只能从头遍历到尾,但是输出却要求从尾到头,这是典型的"先进后出",我们可以想到栈! ArrayList 中有个方法是 add(index,value),可以指定 index 位置插入 value 值 所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置,最后输出 listNode 即可得到逆序链表

3代码
代码语言:javascript
复制
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arlist = new ArrayList<>();
        ListNode ln = listNode;
        while(ln != null){
            arlist.add(0,ln.val);
            ln = ln.next;
        }
        return arlist;
    }
}

4.复杂度

时间复杂度:O(n)O(n) 空间复杂度:O(n)O(n)

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/12/04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Java数据结构-链表
  • 单链表
    • 简单实现
      • 输出:
      • 代码
    • 面试题
      • 1题目描述
      • 2分析
      • 3代码
    • 4.复杂度
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档