【LeetCode】删除链表的倒数第 N 个结点 Java 题解

关注

发布于: 刚刚

题目描述

给你一个链表，删除链表的倒数第 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]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是链表操作题目。在对链表进行操作时，我们常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
根据题目描述，首先对链表进行一次遍历，求出链表的长度，第二次遍历链表，找到目标节点，并指向下一个节点。实现代码如下：

通过代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        if (head == null) {            return head;        }
        ListNode dummy = new ListNode(0);        dummy.next = head;
        int listNodeLength = 0;        while (head != null) {            head = head.next;            listNodeLength++;        }
        ListNode cur = dummy;        for (int i = 1; i < listNodeLength - n + 1; ++i) {            cur = cur.next;        }        cur.next = cur.next.next;
        return dummy.next;    }}

复制代码

总结

上述算法的时间复杂度是 O(n), 空间复杂度是 O(1)
坚持算法每日一题，加油！

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/771b73a5279d731bc57453cf1】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】删除链表的倒数第 N 个结点 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论