面试算法21：删除倒数第k个节点

题目

如果给定一个链表，请问如何删除链表中的倒数第k个节点？假设链表中节点的总数为n，那么1≤k≤n。要求只能遍历链表一次。
例如，输入图4.1（a）中的链表，删除倒数第2个节点之后的链表如图4.1（b）所示。

分析

题目要求只能遍历链表一次。为了实现只遍历链表一次就能找到倒数第k+1个节点，可以定义两个指针。第1个指针P1从链表的头节点开始向前走k步，第2个指针P2保持不动；从第k+1步开始指针P2也从链表的头节点开始和指针P1以相同的速度遍历。由于两个指针的距离始终保持为k，当指针P1指向链表的尾节点时指针P2正好指向倒数第k+1个节点。

解

public class Test {public static void main(String[] args) {ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);listNode1.next = listNode2;listNode2.next = listNode3;listNode3.next = listNode4;listNode4.next = listNode5;listNode5.next = listNode6;ListNode result = removeNthFromEnd(listNode1, 2);while (result != null) {System.out.println(result.val);result = result.next;}}public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode front = head, back = dummy;for (int i = 0; i < n; i++) {front = front.next;}while (front != null) {front = front.next;back = back.next;}back.next = back.next.next;return dummy.next;}
}