删除链表的倒数第k个结点

问题重述：

给你一个链表，删除链表的倒数第 k 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[1,2,3,5]


示例 2：

输入：head = [1], k = 1
输出：[]


示例 3：

输入：head = [1,2], k = 1
输出：[1]


提示：

• 链表中结点的数目为 sz


• 1 <= sz <= 30


• 0 <= Node.val <= 100


• 1 <= k <= sz

问题分析：

本题要求删除倒数第k个结点，重要的是获取删除结点的前一个结点，将该节点的下一个结点指向要删除的节点的下一个结点，常规思路是遍历链表，获得链表长度，然后根据链表长度找到要删除的结点，这种方法需要遍历两次链表。使用双指针的方法可以做到一次遍历就能够找到结点。使用双指针，一个指针从头开始一个指针从第k个开始，然后两个指针一起向后遍历，当快指针到达链表尾部的时候，慢指针对应的刚好是倒数第k+1个结点

解法：

链表遍历、双指针（一次遍历）

解题：

代码：

package test.linklist;
/**
*
* @author FOLDN
* 从长度为n的链表中，删除倒数第k个结点
*
*/
public class DeleteKthNode {
public static void main(String[] args) {

}
public static Node deleteKthNode(Node head,int k) {
/*
if(k <1 || head == null) {
return head;
}
// 方法一，直接遍历链表
// 记录链表的头，因为最后要返回链表的头
Node linkedList = head;
while(linkedList != null) {
// 第一次遍历链表，每经过一个结点，k-1，遍历到最后k = k-n
k = k-1;
linkedList = linkedList.next;
}
// 遍历完链表后，k有三种情况，分别是等于0，大于0，小于0
// k大于0，说明需要删除的结点不存在于链表中,不需要处理，直接返回链表即可
// k等于0，说明要删除的是链表的头节点
if(k == 0) {
// 删除头节点然后返回链表
head = head.next;
}
// k小于0，需要再次进行遍历确定要删除的结点
if(k <0) {
// 第二次遍历需要注意的是此时的linkedList对应的是最后的结点，所以需要重新赋值
linkedList = head;
while(k != 0) {
k = k+1;
linkedList = linkedList.next;
}
// 删除结点
linkedList.next = linkedList.next.next;
}
return head;
*/
// 方法二，使用双指针，只需要使用一次循环
if(k <1 || head == null) {
return head;
}
Node fast = head;
Node slow = head;
for(int i = 0;i fast = fast.next;
}
// 这一步是为了当删除的结点是头结点的时候，可以正常返回
if(fast == null) {
return head.next;
}
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return head;
}
}


代码解析：

链表遍历相当简单，就是先遍历一般确定长度，然后通过长度确定要删除的节点的前一个结点，然后第二次遍历找到要要删除的结点的前一个结点，对链表进行更改

本题我们使用快慢双指针对链表进行遍历，一遍遍历即可确定要删除的结点。首先让快指针fast先向前移动k个位置，此时让fast指针和slow指针一起向后遍历，当fast指针遍历完最后一个节点（即此时的fast结点对应的是链表最后一个结点对应的next，为null）的时候，slow结点对应的结点就是要删除的结点。为了简便删除对应结点，我们可以一开始创建一个哑结点，将该节点的next设为head，这样我们可以处理直接处理当要删除的结点为头节点的问题，并且找到的结点是要删除的节点的下一个结点

总结：

快慢双指针一般用于倒数的元素的处理或者检测会回文序列