Java代码实现：删除链表倒数第 n 个结点
问题描述：
给你一个单向链表，删除链表倒数第n个结点，然后返回head结点。这里的数字n是有效数字。
Given linked list: 1->2->3->4->5, and n = 2.
移除倒数第二个结点之后： 1->2->3->5.
方法一：先遍历获取链表长度，接着获取要移除的前一个元素，修改该元素的node.next --> node.next.next。
image
代码如下：
/**
* 移除链表倒数第n个结点，先遍历获取链表长度，接着获取要移除的前一个元素，修改该元素的node.next --> node.next.next。
*
* @param head
* @param n
* @return
*/
public SingleNode removeNthFromEnd1(SingleNode head, int n) {
SingleNode dummy = new SingleNode(0, head);
//获取链表长度
int length = 0;
SingleNode first = head;
while (first != null) {
length++;
first = first.next;
}
// 找到角标为(length - n - 1)的结点，让其next指向下下一个结点。
first = head;
int index = 0;
while (index < length - n - 1) {
first = first.next;
index++;
}
first.next = first.next.next;
return dummy.next;
}
测试代码如下：
SingleLinkedList sll = new SingleLinkedList();
for (int i = 0; i < 5; i++) {
sll.addLast(i + 1);
}
System.out.println(sll.toString());
SingleNode node1 = removeNthFromEnd1(sll.getFirst(), 2);
sll.logFromHead("removeNthFromEnd1", node1);
输出结果如下：符合预期
I/System.out: SingleLinkedList:[1, 2, 3, 4, 5]
I/System.out: removeNthFromEnd1:[1, 2, 3, 5]
感兴趣的同学可自行修改测试用例。
方法二：使用两个指针，两个指针保持固定间距n+1，接着开始遍历。当前面的指针指向null的时候，后面的那个指针刚好指向要移除的结点前一个，我们让其next指向其next.next即可。
image
/**
* 移除链表倒数第n个结点，使用两个指针实现。
*
* @param head
* @param n
* @return
*/
public SingleNode removeNthFromEnd2(SingleNode head, int n) {
SingleNode dummy = new SingleNode(0, head);
SingleNode left = dummy;
SingleNode right = dummy;
for (int i = 0; i <= n; i++) {
right = right.next;
}
while (right != null) {
left = left.next;
right = right.next;
}
left.next = left.next.next;
return dummy.next;
}
测试代码如下：
SingleLinkedList sll = new SingleLinkedList();
for (int i = 0; i < 5; i++) {
sll.addLast(i + 1);
}
System.out.println(sll.toString());
SingleNode node2 = removeNthFromEnd2(sll.getFirst(), 2);
sll.logFromHead("removeNthFromEnd2", node2);
输出结果如下：跟预期一致。
SingleLinkedList:[1, 2, 3, 4, 5]
removeNthFromEnd2:[1, 2, 3, 5]
完整代码请查看
项目中搜索SingleLinkedList即可。
github传送门 https://github.com/tinyvampirepudge/DataStructureDemo
gitee传送门 https://gitee.com/tinytongtong/DataStructureDemo
