三种方法实现获取链表中的倒数第n个元素

发布时间:2024年01月13日



在这里插入图片描述

先放初始代码

节点类

public class HeroNode {

    public int no;

    public String name;

    public HeroNode next; //指向下一个节点

    public HeroNode(int no, String name, HeroNode next) {
        this.no = no;
        this.name = name;
        this.next = next;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

}

单链表类方法

public class SingleLinkedList {

    /** 初始化头节点 不存放数据 只是一个标记 */
    private HeroNode head = new HeroNode(0, "", null);

    /** 获取链表有效节点长度 */
    public int length(){
        int length = 0;
        HeroNode currentNode = head.next;
        while ( currentNode != null ) {
            length++;
            currentNode = currentNode.next;
        }
        return length;
    }

    /** 插入节点 尾插法 */
    public void add(HeroNode newNode){
        if( newNode == null ){
            return;
        }
        HeroNode currentNode = head;
        while ( currentNode.next != null ) {
            currentNode = currentNode.next;
        }
        currentNode.next = newNode;
    }

    /** 展示列表 */
    public void show(){
        HeroNode currentNode = head.next;
        while ( currentNode != null ) {
            System.out.println(currentNode);
            currentNode = currentNode.next;
        }
    }

}

以上方法定义了一个 节点类 和一个 单链表类,其中单链表类定义了一个基本的尾插法方法 add() 和展示的方法show() ,还有一个获取链表长度的方法 length()


方式1

该方法用于获取链表中倒数第N个节点。在这个方法中,先计算链表的长度 length,然后通过 length - i + 1 找到倒数第 N 个节点的位置。最后,通过遍历链表找到对应的节点并返回。

 /** 获取链表中倒数第N个节点 */
    public HeroNode getNthNodeType1(int i){
        int length;
        if( i < 1 || (length = length()) < i ){
            return null;
        }
        int j = (length - i) + 1;
        HeroNode resultNode = head;
        for (int i1 = 0; i1 < j; i1++) {
            resultNode = resultNode.next;
        }
        return resultNode;
    }

方式2

该方法是使用了一个 HashMap 来存储每一个节点,并使用节点的位置作为键。然后,根据 length - i + 1 找到倒数第N个节点的位置,从 map 中获取对应的节点。

 /** 获取链表中倒数第N个节点 */
    public HeroNode getNthNodeType2(int i){
        if( i < 1 ){
            return null;
        }
        HeroNode resultNode = head;
        Map<Integer, HeroNode> map = new HashMap<>(15);
        int length = 0;
        while ( resultNode.next != null ){
            map.put( ++length, resultNode.next );
            resultNode = resultNode.next;
        }
        return map.get(length - i + 1);
    }


方式3

该方法是在方法内部使用了两个指针 fast 和 slow,通过移动这两个指针,使得它们相差 i 个节点。当 fast 指针到达链表末尾时,slow 指针所指向的节点即为倒数第N个节点。

 /** 获取链表中倒数第N个节点 */
    public HeroNode getNthNodeType3(int i){
        if( i < 1 ){
            return null;
        }
        HeroNode fast = head;
        //  先让快指针领先 i 个节点
        for (int j = 0; j < i; j++) {
            if( fast.next == null ){
                return null;
            }
            fast = fast.next;
        }
        HeroNode slow = head;
        while ( fast != null ){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


在这里插入图片描述



文章来源:https://blog.csdn.net/2301_78386975/article/details/135549621
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。