先放初始代码
节点类
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; }
