一、双指针法
快慢指针的思想。我们将第一个指针 fast 指向链表的第k+1 个节点，第二个指针 slow 指向链表的第一个节点，此时指针fast 与 slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针fast 走到链表的尾部空节点时，则此时slow 指针刚好指向链表的倒数第k个节点。
1.1 链表中倒数第k个节点
public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; // 快指针 指向k+1 while (fast != null && k > 0) { fast = fast.next; k--; } // 快慢指针同时走，快指针指向null的时候，返回slow while (fast != null) { fast = fast.next; slow = slow.next; } return slow;
1.2 删除链表倒数第N个节点
public ListNode removeNthFromEnd(ListNode head, int n) { // 增加头结点 ListNode dummy = new ListNode(0,head); int length = getLength(head); ListNode cur = dummy; for (int i = 0; i < length - n + 1; i++) { cur = cur.next; } cur.next = cur.next.next; // 删除头结点 ListNode ans = dummy.next; return ans; } public int getLength(ListNode head){ int length = 0; while (head!=null){ ++length; head = head.next; } return length; }
