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

简介: 【力扣】19. 删除链表的倒数第 N 个结点

19. 删除链表的倒数第 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

进阶:你能尝试使用一趟扫描实现吗?

解题方法

  • C
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head; // 定义哑节点
    int len = 0;

    if (NULL == head) {
        return head;
    }

    while (head) {
        head = head->next;
        len++; // 计算链表长度
    }

    struct ListNode* cur = dummy;
    for (int i = 1; i < len - n + 1; i++) {
        cur = cur->next; // 找到要移除的节点
    }
    cur->next = cur->next->next; // 移除节点

    struct ListNode* res = dummy->next;
    free(dummy); // 释放内存

    return res;
}

复杂度分析

时间复杂度为 O(L),其中 LLL 是链表的长度。

空间复杂度为 O(1)。

  • C 快慢指针
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {

    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head; // 定义哑节点
    dummy->val = 0;

    struct ListNode* fast = head; // 定义双指针
    struct ListNode* slow = dummy;

    for (int i = 0; i < n; i++) {
        fast = fast->next; // 快指针先移动 n 个节点
    }

    while (fast) {
        fast = fast->next; // 同步移动,直到快指针到达末尾
        slow = slow->next;
    }

    slow->next = slow->next->next; // 移除节点

    struct ListNode* res = dummy->next;
    free(dummy); // 释放内存

    return res;
}

复杂度分析

时间复杂度为 O(L),其中 LLL 是链表的长度。

空间复杂度为 O(1)。


相关文章
|
1月前
链表的中间结点
链表的中间结点
173 57
|
2月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
2月前
|
存储 算法
LeetCode第86题分隔链表
文章介绍了LeetCode第86题"分隔链表"的解法,通过创建两个新链表分别存储小于和大于等于给定值x的节点,然后合并这两个链表来解决问题,提供了一种简单易懂且操作原链表的解决方案。
LeetCode第86题分隔链表
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
C++ 索引
leetcode 707.设计链表
本文提供了解决LeetCode 707题"设计链表"的C++实现,包括单链表的节点定义和类方法实现,如添加节点、获取节点值、删除节点等。
|
2月前
|
算法
LeetCode第92题反转链表 II
文章分享了LeetCode第92题"反转链表 II"的解法,通过使用四个指针来记录和更新反转链表段的头部、尾部以及前一个和后一个节点,提供了一种清晰且易于理解的解决方案。
LeetCode第92题反转链表 II
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
33 2
|
5月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
46 1