删除链表结点类问题

🚀 优质资源分享 🚀

删除链表结点

NO1. 删除链表倒数第 k个结点

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针。要求：空间复杂度 O(1)O(1)O(1)，时间复杂度 O(n)O(n)O(n)

如果倒数第 k 个结点刚好是头结点，那头结点需要特殊处理。为了各个结点能等同操作，设置一个虚拟头结点。

寻找倒数第 k 个结点常使用“快慢双指针”来实现。

算法流程：

• step 1 ：在原头结点前面添加一个虚拟头结点；
• step 2 ：使用快慢指针找到倒数第 k+1 个结点（有了前驱结点，第 k 个结点才能删掉）；
• step 3 ：删除倒数第 k 个结点，返回头结点；

代码实现：

java

public class Solution {
    static class ListNode {
        int val;
        ListNode next = null;
    }
    
    public ListNode removeNthFromEnd (ListNode head, int k) {
        // 1. 添加一个虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 2. 使用快慢指针找到倒数第 k+1 个结点
        ListNode prev = getNode(dummy, n);
        // 3. 删除 倒数 第 k 个结点
        prev.next = prev.next.next;
        return dummy.next;
    }
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16