博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
查找单链表中的倒数第 k 个结点
阅读量:172 次
发布时间:2019-02-28

本文共 7896 字,大约阅读时间需要 26 分钟。

一 代码

package com.atguigu.linkedlist;/*** @className: SingleLinkedListDemo* @description: 单链表测试* @date: 2021/2/28* @author: cakin*/public class SingleLinkedListDemo {    /**     * 功能描述:单链表测试     *     * @param args 命令行     * @author cakin     * @date 2021/2/28     */    public static void main(String[] args) {        // 先创建节点        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");        HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");        HeroNode hero3 = new HeroNode(3, "吴用", "智多星");        HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");        // 创建单链表        SingleLinkedList singleLinkedList = new SingleLinkedList();        // 按照编号加入链表        singleLinkedList.addByOrder(hero1);        singleLinkedList.addByOrder(hero4);        singleLinkedList.addByOrder(hero2);        singleLinkedList.addByOrder(hero3);        // 显示        singleLinkedList.list();        // 修改节点        HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");        singleLinkedList.update(newHeroNode);        System.out.println("修改后的链表");        singleLinkedList.list();        // 删除一个节点        singleLinkedList.del(1);        singleLinkedList.del(4);        System.out.println("删除后的链表");        singleLinkedList.list();        // 测试一下看看是否得到了倒数第K个节点        HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);        System.out.println("res=" + res);    }    /**     * 功能描述:查找单链表中的倒数第k个结点     *     * @param head  头结点     * @param index 倒数第index个节点     * @return HeroNode 倒数第index个节点     * @author cakin     * @date 2021/3/1     * @description: 思路     * 1 编写一个方法,接收head节点,同时接收一个index     * 2 index 表示是倒数第index个节点     * 3 先把链表从头到尾遍历,得到链表的总的长度 getLength     * 4 得到size后,我们从链表的第一个开始遍历 (size-index)个,就可以得到     * 5 如果找到了,则返回该节点,否则返回null     */    public static HeroNode findLastIndexNode(HeroNode head, int index) {        // 判断如果链表为空,返回null        if (head.next == null) {            return null; // 没有找到        }        // 链表的长度(节点个数)        int size = getLength(head);        // index的校验        if (index <= 0 || index > size) {            return null;        }        // 定义辅助变量        HeroNode cur = head.next; //3 // 3 - 1 = 2        // 遍历 size-index 位置,就是我们倒数的第K个节点        for (int i = 0; i < size - index; i++) {            cur = cur.next;        }        return cur;    }    /**     * 功能描述:获取单链表的有效节点节点的个数(如果是带头结点的链表,需求不统计头节点)     *     * @param head 链表的头节点     * @return 返回的就是有效节点的个数     * @author cakin     * @date 2021/3/1     */    public static int getLength(HeroNode head) {        if (head.next == null) { // 空链表            return 0;        }        int length = 0;        // 定义一个辅助的变量, 这里我们没有统计头节点        HeroNode cur = head.next;        while (cur != null) {            length++;            cur = cur.next; //遍历        }        return length;    }}/*** @className: SingleLinkedListDemo* @description: 单向链表,用来管理英雄* @date: 2021/2/28* @author: cakin*/class SingleLinkedList {    // 先初始化一个头节点, 头节点不能动, 不存放具体的数据    private HeroNode head = new HeroNode(0, "", "");    // 返回头节点    public HeroNode getHead() {        return head;    }    /**     * 功能描述:添加英雄节点到单向链表     *     * @param heroNode 英雄节点     * @author cakin     * @date 2021/2/28     * @description: 当不考虑编号顺序时的添加     * 1 找到当前链表的最后节点     * 2 将最后这个节点的next 指向 新的节点     */    public void add(HeroNode heroNode) {        // 因为head节点不能动,因此需要一个辅助变量 temp        HeroNode temp = head;        // 遍历链表,找到最后        while (true) {            // 找到链表的最后            if (temp.next == null) {                break;            }            // 如果没有找到最后, 将temp后移            temp = temp.next;        }        // 当退出while循环时,temp就指向了链表的最后        // 将最后这个节点的next指向新的节点        temp.next = heroNode;    }    /**     * 功能描述:添加英雄时,根据排名将英雄插入到指定位置     *     * @param heroNode 英雄节点     * @author cakin     * @date 2021/2/28     * @description: 如果有这个排名,则添加失败,并给出提示     */    public void addByOrder(HeroNode heroNode) {        // 因为头节点不能动,因此我们仍然通过一个辅助变量来帮助找到添加的位置        // 因为是单链表,所以我们找的temp是位于添加位置的前一个节点,否则插入不了        HeroNode temp = head;        // flag标志添加的编号是否存在,默认为false        boolean flag = false;        while (true) {            // 说明temp已经在链表的最后            if (temp.next == null) {                break;            }            // 位置找到,就在temp的后面插入            if (temp.next.no > heroNode.no) {                break;            } else if (temp.next.no == heroNode.no) { // 希望添加的heroNode的编号已然存在                flag = true; // 编号存在                break;            }            temp = temp.next; //后移        }        // 不能添加,编号存在        if (flag) {            System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);        } else {            // 插入到链表中, 插入到temp的后面            heroNode.next = temp.next;            temp.next = heroNode;        }    }    /**     * 功能描述:修改节点的信息, 根据no编号来修改,即no编号不能改     *     * @param newHeroNode 待修改的英雄节点     * @author cakin     * @date 2021/2/28     */    public void update(HeroNode newHeroNode) {        // 判断是否空        if (head.next == null) {            System.out.println("链表为空");            return;        }        // 根据no编号,找到需要修改的节点,        // 定义一个辅助变量        HeroNode temp = head.next;        //表示是否找到该节点        boolean flag = false;        while (true) {            if (temp == null) {                break; // 已经遍历完链表            }            if (temp.no == newHeroNode.no) {                // 找到                flag = true;                break;            }            temp = temp.next;        }        // 根据flag判断是否找到要修改的节点        if (flag) {            temp.name = newHeroNode.name;            temp.nickname = newHeroNode.nickname;        } else { // 没有找到            System.out.printf("没有找到编号 %d 的节点,不能修改\n", newHeroNode.no);        }    }    /**     * 功能描述:删除节点     *     * @param no 待删除节点     * @author cakin     * @date 2021/2/28     * @description: 思路     * 1 head 不能动,因此我们需要一个temp辅助节点找到待删除节点的前一个节点     * 2 说明我们在比较时,是temp.next.no和需要删除的节点的no比较     */    public void del(int no) {        HeroNode temp = head;        boolean flag = false; // 标志是否找到待删除节点的        while (true) {            if (temp.next == null) { // 已经到链表的最后                break;            }            if (temp.next.no == no) {                // 找到的待删除节点的前一个节点temp                flag = true;                break;            }            temp = temp.next; // temp后移,遍历        }        // 判断flag        if (flag) { // 找到            // 可以删除            temp.next = temp.next.next;        } else {            System.out.printf("要删除的 %d 节点不存在\n", no);        }    }    // 显示链表    public void list() {        // 判断链表是否为空        if (head.next == null) {            System.out.println("链表为空");            return;        }        // 因为头节点,不能动,因此我们需要一个辅助变量来遍历        HeroNode temp = head.next;        while (true) {            // 判断是否到链表最后            if (temp == null) {                break;            }            // 输出节点的信息            System.out.println(temp);            //将temp后移            temp = temp.next;        }    }}/*** @className: SingleLinkedListDemo* @description: 定义HeroNode , 每个HeroNode对象就是一个节点* @date: 2021/2/28* @author: cakin*/class HeroNode {    public int no; // 编号    public String name; // 姓名    public String nickname; // 昵称    public HeroNode next; // 指向下一个节点    // 构造器    public HeroNode(int no, String name, String nickname) {        this.no = no;        this.name = name;        this.nickname = nickname;    }    // 为了显示方便,重新toString    @Override    public String toString() {        return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";    }}

二 测试

HeroNode [no=1, name=宋江, nickname=及时雨]HeroNode [no=2, name=卢俊义, nickname=玉麒麟]HeroNode [no=3, name=吴用, nickname=智多星]HeroNode [no=4, name=林冲, nickname=豹子头]修改后的链表HeroNode [no=1, name=宋江, nickname=及时雨]HeroNode [no=2, name=小卢, nickname=玉麒麟~~]HeroNode [no=3, name=吴用, nickname=智多星]HeroNode [no=4, name=林冲, nickname=豹子头]删除后的链表HeroNode [no=2, name=小卢, nickname=玉麒麟~~]HeroNode [no=3, name=吴用, nickname=智多星]res=HeroNode [no=2, name=小卢, nickname=玉麒麟~~]

 

转载地址:http://xzhj.baihongyu.com/

你可能感兴趣的文章