首页 > 删除链表的倒数第N个节点
头像
蘑菇睡不着
编辑于 2021-05-30 23:20
+ 关注

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

一、题目描述

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

示例 1:

输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]

示例 2:

输入:head = [1], n = 1
输出:[]

示例 3:

输入:head = [1,2], n = 1
输出:[1]

提示:
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

二、思路分析:

  这道题的包含两个问题:一是:怎么找到倒数第 N 个节点;二是:怎么删除一个节点。
  先说怎么删除一个节点吧。其实也很简单,那就是要被删除节点的前置节点的next指针,指向被删除节点的下一个节点即可。代码片段为:node.next = node.next.next;其中 node 为 被删除节点的前置节点。
  再说说怎么找到倒数第 N 个节点。这个就有讲头了,主要有两种方法:

  1. 双指针法:定义两个快慢指针,快指针先走 N 步,然后快慢指针一起往后走,直到快指针到链表末尾。此时,慢指针就是被删除指针的前置节点,然后怎么删除就不用我说了吧。
  2. 利用栈:将链表按顺序压入栈中,然后开始往外弹出元素,弹 N 次,弹完 N 次后,在弹出一个元素,这个元素就是 被删除节点的前置节点。

接下来会用两端代码来实现这两种方法。

三、AC代码

方法一:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return head;
        }
        // 定义哑节点,主要是为了防止当 头节点也被删除的情况
        ListNode listNode = new ListNode(0, head);
        // 快指针
        ListNode fast = listNode;
        // 慢指针
        ListNode slow = listNode;
        // 快指针先走 N 步
        while(n > 0 && fast.next != null) {
            fast = fast.next;
            n --;
        }

        if (n > 0) {
            return listNode.next;
        }
        // 快慢指针一起走
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 如果说被删除节点是倒数第一个节点,那么就直接置为null
        if (slow.next == null || slow.next.next == null)         {
            slow.next = null;
            return listNode.next;
        }
        // 删除节点
        slow.next = slow.next.next;
        return listNode.next;

    }
}

时间复杂度:O(n),其中 n 是链表的长度,要遍历一次链表
空间复杂度:O(1)。

方法二:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head
        // 定义栈
        Deque<ListNode> stack = new LinkedList<ListNode>();
        ListNode cur = dummy;
        // 按顺序压入栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 弹出 N 个元素
        for (int i = 0; i < n; ++i) {
            stack.pop();
        }
        // 在弹出一个(注意这里是弹出但不删除节点),作为被删除节点的前置节点
        ListNode prev = stack.peek();
        // 删除节点
        prev.next = prev.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

时间复杂度:O(n),其中 n 是链表的长度,要遍历一次链表
空间复杂度: O(n),其中 n 是链表的长度。主要为栈的开销

四、总结

  这道题整体难度还可以,难点就是要知道如何正确的删除节点,以及如果正确的找到被删除的节点。其实删除节点还有很多办法,比如:将被删除节点的next节点的值赋给自己,然后将被删除节点的next节点删除也可以到达所要的效果。

如果觉得文章还不错就点个赞、关个注呗~

全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

近期精华帖

热门推荐