三种方法实现获取链表中的倒数第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月前
19 删除链表的倒数第 N 个结点
19 删除链表的倒数第 N 个结点
|
12天前
|
算法
数据结构和算法学习记录——习题-移除链表元素
数据结构和算法学习记录——习题-移除链表元素
9 0
|
3天前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
8天前
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】
|
8天前
|
存储 SQL 算法
LeetCode 题目 82:删除排序链表中的重复元素 II
LeetCode 题目 82:删除排序链表中的重复元素 II
|
8天前
|
SQL 算法 数据挖掘
力扣题目 19:删除链表的倒数第N个节点 【python】
力扣题目 19:删除链表的倒数第N个节点 【python】
|
12天前
|
存储 NoSQL Redis
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
Redis第四弹,Redis实现list时候做出的优化ziplist(压缩链表,元素少的情况),可更好的节省空间list——(内部编码:quicklist)Object encoding
|
20天前
题目----力扣--移除链表元素
题目----力扣--移除链表元素
21 1
|
22天前
|
索引
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
【力扣刷题】删除链表的倒数第 N 个结点、两两交换链表中的节点、随机链表的复制
20 0
|
22天前
|
存储 算法 索引
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
【力扣刷题】只出现一次的数字、多数元素、环形链表 II、两数相加
26 1