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

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

先放初始代码


节点类

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;
    }
相关文章
|
1月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
35 1
|
1月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
65 1
|
3月前
|
程序员
【刷题记录】移除链表元素
【刷题记录】移除链表元素
|
1月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
41 0
Leetcode第十九题(删除链表的倒数第N个节点)
01_移除链表元素
01_移除链表元素
|
1月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
49 0
|
1月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
16 0
|
1月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
29 0
|
3月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点