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

飞熊 • 2024年1月17日下午4:49 • 技术随笔 • 阅读 310

文章目录

先放初始代码
方式1
方式2
方式3

先放初始代码

节点类

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;
    }