Loading...
墨滴

北鱼扶摇

2021/11/06  阅读:17  主题:默认主题

躬行算法之删除链表的倒数第 N 个结点

删除链表的倒数第N个节点
删除链表的倒数第N个节点

Leetcode P19.

这道题目,需要注意,这里的链表是单向链表。因为没有逆向指针,所谓“倒序第 n 个节点”,便无从说起。我们可以转换思路,倒序第 n 个节点,在一个大小为 sz 的链表中,同时也会是正序第 sz+1-n 个节点。 遍历链表,同时计数 i,直到末尾, i==sz,此过程中可能出现如下情况:

  1. 遍历部分不够长,第 i+1-n 个节点尚未出现,即 i+1-n <= 0,
  2. 遍历部分长度达到临界值,第 i+1-n 个节点恰好出现,即首次出现 i+1-n > 0;
  3. 遍历部分足够长,直到末尾,第 i+1-n 个节点在游标指针的落后位置,也就是更靠近链表 head 的位置,当然此过程中的 i+1-n > 0 依然是成立的。

基于这种思路,考虑使用快慢指针,快指针指向链表尾部,遍历链表,慢指针指向目标节点。在这个题中,因为还要移除目标指针,所以还需要一个额外的指针,指向目标节点的 prev 节点,该指针应滞后一步于慢指针。

各指针移动过程如下:

  1. 快指针先移动,i 随着快指针的移动渐增,慢指针尚未开始移动;
  2. 快指针移动,直到临界点,正序第 sz+1-n 个节点出现,此时 i+1-n > 0 ,此时慢指针准备开始移动,指向 head;
  3. 快慢指针移动,滞后一步于慢指针的 prev 指向旧的慢指针,也开始移动;
  4. 快、慢、滞后指针分别移动,直到快指针遍历完整个链表,三个指针停止移动;

此时,判断慢指针即为待移除的节点。判断慢指针处于的几种状态即可: 慢指针从未移动(slow==null)、 慢指针恰巧指向第一个节点而滞后指针尚未有指向(slow==head && prev==null)、 慢指针移动到某个未知而之后指针也已开始移动(slow!=null && prev!=null)。

根据分析,写出代码:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = null// 目标节点
        ListNode prev = null;
        int i = 1;
        while (fast != null) {
            fast = fast.next;
            i++;
            if (i + 1 - n > 0) {
                if (slow == null) {
                    slow = head;
                } else {
                    prev = slow;
                    slow = slow.next;
                }
            }
        }
        if (slow == null) {
            return head;
        }
        if (prev == null) {
            return slow.next;
        } else {
            prev.next = slow.next;
            return head;
        }
    }
}

链表节点结构定义

class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) { this.val = val; }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

北鱼扶摇

2021/11/06  阅读:17  主题:默认主题

作者介绍

北鱼扶摇