题目
**分别实现两个函数，一个可以删除单链表中倒数第 K 个节点，另一个可以删除双链表中倒数第 K 个节点
要求
如果链表长度为 N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
思路
本题较为简单，实现方式也是多种多样的，小编提供一种方法供读者参考。
先来看看单链表如何调整。如果链表为空或者 K 小于1。这种情况下，参数是无效的直接返回即可，除此之外，让链表从头开始走到尾，每移动一步，就让K的值减1。
链表: 1 → 2 → 3，K = 4，链表根本不存在倒数第4个节点
走到的节点: 1 → 2 → 3
K 变化为: 3 2 1
链表: 1 → 2 → 3，K ＝ 3，链表倒数第3个节点是1节点
走到的节点: 1 → 2 → 3
K 变化为: 2 1 0
链表: 1 → 2 → 3，K ＝ 2，链表倒数第2个节点是2节点
链表:走到的节点: 1 → 2 → 3
K 变化为:1 → 0 → 1
由以上三种情况可知，让链表从头开始走到尾，没移动一步，就让 K 值减1，当链表走到结尾时，如果值大于0。说明不用调整链表，因为链表根本没有倒数第 K 个节点，此时将原链表直接返回即可；如果 K 值等于0，说明链表倒数第 K 个节点就是头节点，此时直接返回head.next，也就是原链表的第二个节点，让第二个节点作为链表的头节点返回即可，相当于删除头节点；接下来，说明一下如果 K 值小于0，该如何处理。
先明确一点，如果要删除链表的头节点之后的某个节点，实际上需要找到要删除节点的前个节点，比如: 1 → 2 → 3，如果想除节点2，则需要找到节点1，然后把节点1连到节点3上(1 → 3)，以此来达到删除节点2的目的。
如果 K 值小于0，如何找到要删除节点的前一个节点呢?方法如下:
1.重新从头节点开始走，每移动一步，就让K的值加1。
2.当K等于0时，移动停止，移动到的节点就是要删除节点的前一个节点。
这样做是非常好理解的，因为如果链表长度为N，要删除倒数第K个节点，很明显，倒数第 K 个节点的前一个节点就是第 N - K 个节点。在第一次遍历后，K 的值变为 K - N。第二次遍历时 K 的值不断加1，加到 0 就停止遍历，第二次遍历当然会停到第 N - K个节点的位置。
代码演示
package com.itz.zcy.listQuestion;
/**
* 分别实现两个函数，一个可以删除单链表中倒数第 K 个节点，另一个可以删除双链表中倒数第 K 个节点
* 如果链表长度为 N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。
*/
public class DeleteListKNode {
/**
* 定义节点
*/
public static class Node {
public int value;
public Node next;
//该变量用来做双链表的指向前区节点，在单链表的时候请读者忽略该节点
public Node last;
public Node(int data) {
this.value = data;
}
}
/**
* 删除单链表的倒数第k个节点
* @param head
* @param lastKth
* @return
*/
public static Node removeLastKthNode(Node head, int lastKth) {
// 异常判定
if (head == null || lastKth < 1) {
return head;
}
// 辅助节点
Node cur = head;
// 遍历一遍节点判断节点在链表的哪儿
while (cur != null) {
lastKth--;
cur = cur.next;
}
// 如果是删除头节点的情况
if (lastKth == 0){
head = head.next;
}
// 找到要删除的节点
if (lastKth < 0) {
cur = head;
while (++lastKth != 0) {
cur = cur.next;
}
// 删除节点
cur.next = cur.next.next;
}
return head;
}
/**
* 删除双链表的倒数第k个节点
* @param head
* @param lastKth
* @return
*/
public static Node removeLastKthDoubleNode(Node head,int lastKth){
if (head==null||lastKth<1){
return head;
}
Node cur = head;
while (cur !=null){
lastKth--;
cur = cur.next;
}
if (lastKth == 0){
head = head.next;
head.last = null;
}
if (lastKth<0){
cur = head;
while (++lastKth!=0){
cur = cur.next;
}
// 删除节点 删除双链表的某个节点
Node newNext = cur.next.next;
cur.next = newNext;
if (newNext != null){
newNext.last = cur;
}
}
return head;
}
public static void main(String[] args) {
Node node = new Node(2);
node.next = new Node(4);
node.next.next = new Node(6);
node.next.next.next = new Node(8);
node.next.next.next.next = new Node(3);
node.next.next.next.next.next = new Node(5);
node.next.next.next.next.next.next = new Node(7);
Node head = removeLastKthNode(node, 5);
while (true){
if (head!=null){
if (head.next == null){
System.out.print(head.value);
}else {
System.out.print(head.value+" → ");
}
}else {
break;
}
head = head.next;
}
System.out.println();
Node node2 = new Node(2);
node2.next = new Node(4);
node2.next.last= node2;
node2.next.next = new Node(6);
node2.next.next.last = node2.next;
node2.next.next.next = new Node(8);
node2.next.next.next.last = node2.next.next;
node2.next.next.next.next = new Node(3);
node2.next.next.next.next.last = node2.next.next.next;
node2.next.next.next.next.next = new Node(5);
node2.next.next.next.next.next.last = node2.next.next.next.next;
node2.next.next.next.next.next.next = new Node(7);
node2.next.next.next.next.next.next.last = node2.next.next.next.next.next;
Node head2 = removeLastKthDoubleNode(node2, 5);
while (true){
if (head2!=null){
if (head2.next == null){
System.out.print(head2.value);
}else {
System.out.print(head2.value+" ⇄ ");
}
}else {
break;
}
head2 = head2.next;
}
}
// 2 → 4 → 8 → 3 → 5 → 7
// 2 ⇄ 4 ⇄ 8 ⇄ 3 ⇄ 5 ⇄ 7
}
总结
该题目比较简单，方法多种多样；时间复杂度是O(n),空间复杂度O(1)。
文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！
