如何删除给定单向链表的倒数第N个元素?
先分析下有哪些关键词:
1. 单向链表,那也就是我们只能单向遍历;
2. 倒数第N个元素,只能先遍历到尾部,才知道倒数第N个元素是什么,但问题又出现了,是单向链表,不能反向遍历,那该如何解决呢?
3. 删除,要想删除某一元素,是需要知道这个指定元素的前一元素才行,那我们其实要找到的倒数N+1个元素.
以如下队列为例,如果要删除倒数第2个元素,就要找到倒数第3个元素,也就是倒数第N+1个元素,那改如何做呢?
首先一定需要一个指针遍历到队列尾部的,那怎么记录这个指针已经遍历过的元素呢?可否也用一个指针记录呢.
按这个思路,首先需要一个正常的指针一直遍历到队列尾部,称之为快指针;
再需要一个比这个快指针慢N个元素的第二个指针,称之为慢指针.
两个指针按照同样的速度同时移动,当快指针到达结尾的时候,慢指针也就到达了倒数第N+1个元素的位置.
再细分下,如果要删除的目标元素正好和链表长度相同呢?那是没有前一个元素的,看来边界值需要稍做处理下,遍历的count值和N值相同时,需要直接删除首元素,不再查找前一元素
附上代码:
public class DeleteNElementFromBottom {
static Node deleteNElementFromBottom(Node head, int n) {
Node quickNode = head;
Node slowNode = null;
int count = 0;
while (quickNode != null) {
if (slowNode == null && count == n) {
// 快指针已经移动过N个元素之后,慢指针才会指向链表头元素
slowNode = head;
} else if (slowNode != null) {
// 慢指针后移
slowNode = slowNode.next;
}
// 快指针后移
quickNode = quickNode.next;
// 计数,用于判断慢指针开始指向头元素时机
// 以及,链表边界值问题
count++;
if (quickNode == null) {
break;
}
}
if (count == n) {
// 删除元素正好是边界值时,返回链表第二个元素做为新链表首元素
return head.next;
} else {
if (null != slowNode) {
// 将被删除的指定元素后一元素接到前一元素上
slowNode.next = slowNode.next.next;
}
return head;
}
}
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
System.out.println(print(node1));
Node backward = deleteNElementFromBottom(node1, 2);
System.out.println(backward);
}
static String print(Node head) {
StringBuilder sb = new StringBuilder("Head->");
Node p = head;
while (p != null) {
sb.append(p.data).append("->");
p = p.next;
}
sb.append("null");
return sb.toString();
}
static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
@Override
public String toString() {
return "Node{data=" + data + ", next=" + next + '}';
}
}
}