java 单链表 练习

练习一下java单链表的简单习题

package com.test1;

import java.util.Stack;

public class SingleListDemo {
    
    /**
     * 返回单链表的总长度
     * @param sl
     * @return
     */
    public static <T> int getListLength(SingleList<T> sl) {
        Node<T> temp = sl.headNode.next;
        int index = 0;
        while(temp != null) {
            temp = temp.next;
            index++;
        }
        return index;
    }
    
    /**
     * 查找单链表中倒数第k个元素
     * @param sl
     * @param k
     * @return
     */
    public static <T> Node<T> getLastK(SingleList<T> sl, int k){
        int length = getListLength(sl);
        if(length < k) {
            throw new RuntimeException("不存在倒数第" + k + "个节点");
        }
        int index = length - k;
        Node<T> temp = sl.headNode.next;
        while(index != 0) {
            temp = temp.next;
            index--;
        }
        return temp;
    }
    
    /**
     * 单链表的反转
     * @param <T>
     * @param args
     */
    public static <T> void reverseList(SingleList<T> sl){
        int length = getListLength(sl);
        if(length == 1) {
            return;
        }
        
        Node<T> headNode = sl.headNode;
        Node<T> last =  headNode.next;
        Node<T> cur = last.next;
        Node<T> next = cur.next;
        last.next = null;
        while(next != null) {
            cur.next = last;
            last = cur;
            cur = next;
            next = next.next;
        }
        cur.next = last;
        sl.headNode.next = cur;
    }
    
    /**
     * 从尾到头打印单链表 (利用栈)
     * @param <T>
     * @param args
     */
    public static <T> void printReverseList1(SingleList<T> sl) {
        Node<T> temp = sl.headNode.next;
        Stack<T> stack = new Stack<>();
        while(temp != null) {
            stack.push(temp.data);
            temp = temp.next;
        }
        while(!stack.empty()) {
            System.out.println(stack.pop());
        }
    }
    
    /**
     * 从尾到头打印单链表 (利用递归) 很是牛逼!
     * @param <T>
     * @param args
     */
    public static <T> void printReverseList2(Node<T> node) {
        if(node.next != null) {
            printReverseList2(node.next);
        }
        System.out.println(node.data);
    }
    
    /**
     * 合并两个有序的单链表,合并之后的单链表任然有序
     * @param <T>
     * @param args
     */
    public static <T> SingleList<T> mergeTwoList(SingleList<T> sl1, SingleList<T> sl2) {
        SingleList<T> result = new SingleList<>();
        Node<T> temp1 = sl1.headNode.next;
        Node<T> temp2 = sl2.headNode.next;
        while(temp1 != null && temp2 != null) {
            if(temp1.compareTo(temp2) < 0) {
                Node<T> temp = temp1;
                temp1 = temp1.next;
                temp.next = null;
                result.addNode(temp);
            } else {
                Node<T> temp = temp2;
                temp2 = temp2.next;
                temp.next = null;
                result.addNode(temp);
            }
        }
        Node<T> temp = temp1 == null ? temp2 : temp1;
        while(temp != null) {
            result.addNode(temp);
            temp = temp.next;
        }
        return result;
    }
    
    public static void main(String[] args) {
//      SingleList<String> sl = new SingleList<>();
//      sl.addNode(new Node<>("李四", null));
//      sl.addNode(new Node<>("张三", null));
//      sl.addNode(new Node<>("王五", null));
//      sl.addNode(new Node<>("赵六", null));
//      sl.showData();
//      System.out.println(getListLength(sl));
//      Node<String> node = getLastK(sl, 2);
//      System.out.println(node);
//      reverseList(sl);
//      System.out.println("\n反转之后为:");
//      sl.showData();
//      System.out.println("\n从尾到头打印单链表");
//      printReverseList2(sl.headNode.next);
//      Node<Integer> a = new Node<>(1, null);
//      Node<Integer> b = new Node<>(2, null);
//      System.out.println(a.compareTo(b));
        
        SingleList<Integer> sl = new SingleList<>();
        sl.addNodeOrder(new Node<>(1, null));
        sl.addNodeOrder(new Node<>(3, null));
        sl.addNodeOrder(new Node<>(70, null));
        sl.addNodeOrder(new Node<>(2, null));
        sl.showData();
        SingleList<Integer> sl1 = new SingleList<>();
        sl1.addNodeOrder(new Node<>(11, null));
        sl1.addNodeOrder(new Node<>(13, null));
        sl1.addNodeOrder(new Node<>(17, null));
        sl1.addNodeOrder(new Node<>(12, null));
        sl1.showData();
        System.out.println("\n合并之后为:");
        SingleList<Integer> result = mergeTwoList(sl, sl1);
        result.showData();
    }
}

class Node<T> implements Comparable<Node<T>>{
    public T data;
    public Node<T> next;
    public Node(T data, Node<T> next) {
        super();
        this.data = data;
        this.next = next;
    }
    @Override
    public String toString() {
        return this.data.toString();
    }
    
    
    @SuppressWarnings("unchecked")
    @Override
    public int compareTo(Node<T> o) {
        if(o.data instanceof Comparable) {
            return ((Comparable<Comparable<?>>) this.data).compareTo((Comparable<?>) o.data);
        }
        return 0;
    }
    
}

class SingleList<T>{
    public Node<T> headNode = new Node<>(null, null);
    
    /**
     * 往尾部添加节点
     * @param node
     */
    public void addNode(Node<T> node) {
        Node<T> temp = headNode;
        while(temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }
    
    /**
     * 按照节点的大小添加节点,使得链表有序
     */
    public void addNodeOrder(Node<T> node) {
        Node<T> last = headNode;
        Node<T> temp = last.next;
        while(temp != null && temp.compareTo(node) < 0) {
            last = temp;
            temp = temp.next;
        }
        if(temp != null && temp.compareTo(node) == 0) {
            throw new RuntimeException("已经存在相同的节点,不允许再次添加");
        }
        last.next = node;
        node.next = temp;
    }
    
    /**
     * 显示list中的数据
     */
    public void showData() {
        Node<T> temp = headNode.next;
        while(temp != null) {
            System.out.print(temp + " ");
            temp = temp.next;
        }
    }
    
    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • javascript 异或运算符实现简单的密码加密功能

    Theone67
  • 使用js获取url中的get参数并转成json格式

    Theone67
  • 当使用junit4 对spring框架中各层进行测试时,需要添加的配置

    当使用junit4 对spring框架中controller/service/mapper各层进行测试时,需要添加的配置

    Theone67
  • 干货十足!张小龙公开课现场玩「跳一跳」,曾拿过 6000 多分

    2017 年 1 月 15 日,微信公开课 PRO 版如约在广州保利世贸博览馆举行。

    知晓君
  • Python 进阶(七): Word 基本操作

    Word 是一个十分常用的文字处理工具,通常我们都是手动来操作它,本节我们来看一下如何通过 Python 来操作。

    Python小二
  • Python中的str字符串

    字符串是有序的字符集合使用单引号【’】、双引号【”】、三引号【”””或者’’’】字符串是不可不变对象Python3.0起,字符串就是Unicode类型(utf8...

    用户7886150
  • PHP统计目录总大小、文件和子目录个数

    php function getDirectorySize($path) { $totalsize = 0; $totalcount = 0; $...

    苦咖啡
  • 电商直播两条路:孵化红人卖货给粉丝,或者用直播服务消费者

    这不是愚人节的玩笑,而是罗永浩的正经带货。三个小时,累计观看销售1.1亿元,这是他的带货成绩单。

    刘旷
  • 【leetcode刷题】20T2-两数相加

    https://leetcode-cn.com/problems/add-two-numbers/

    木又AI帮
  • 软技能提升:转转中后台规范落地实践

    中台覆盖了多线业务,自然对应的不少后台系统,考虑日后到项目应用,满足业务的快速迭代,无论是技术版本升级、敏捷开发、可复用性和可维护性等。

    前端迷

扫码关注云+社区

领取腾讯云代金券