【LeetCode】19. 删除链表的倒数第 N 个结点

in programming •  2 months ago 

1 题目描述

19. 删除链表的倒数第 N 个结点要求给定一个链表,任务是删除链表的倒数第 n 个结点,并且返回链表的头结点。

2 解题思路

本题可以通过双指针的方法来解决。具体来说,可以使用两个指针 slowfast,它们都初始化在哑节点 dummy 上。fast 指针先向前移动 n + 1 步,然后两个指针同时移动,直到 fast 指针到达链表的末尾。这时,slow 指针恰好位于要删除节点的前一个位置。删除该节点后,返回哑节点的 next 指针即可。

3 Java 代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head); // 创建一个哑节点作为头结点
        ListNode fast = dummy, slow = dummy;

        // 让 fast 指针先走 n+1 步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 同时移动 fast 和 slow 指针,直到 fast 到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除目标节点
        slow.next = slow.next.next;

        return dummy.next;
    }
}
  • 时间复杂度: O(L),其中 L 是链表的长度。每个节点只遍历一次。
  • 空间复杂度: O(1),只用了常量级别的额外空间。

4 注意事项

  • 哑节点:引入哑节点 dummy 以简化代码逻辑,避免处理头节点的特殊情况。
  • 双指针:使用两个指针 slowfastfast 指针先前进 n + 1 步,确保当 fast 指针到达链表末尾时,slow 指针位于要删除节点的前一个位置。
  • 删除节点:当 fast 指针到达链表末尾时,slow 指针指向要删除节点的前一个位置,通过 slow.next = slow.next.next 完成删除操作。
  • 返回新头节点:返回 dummy.next 作为新的链表头节点。
Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!