LeetCode 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

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

法一:双指针法,第一个指针先往前走n步,然后两个指针一起向尾部移动,直到第二个指针指向尾指针:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    ret := head

    aheadNode := head
    for i := 0; i < n; i ++ {
        aheadNode = aheadNode.Next
    }

    // 如果要删除头节点,特殊处理一下
    if aheadNode == nil {
        return ret.Next
    }

    for aheadNode.Next != nil {
        head = head.Next
        aheadNode = aheadNode.Next
    }

    // 删除结点
    head.Next = head.Next.Next

    return ret
}

如果链表有n个结点,此算法时间复杂度为O(n),空间复杂度为O(1),且只遍历了一次链表。

法二:将链表中所有结点入栈,然后一个一个出栈,直到出栈n个结点,即找到了要删除的结点:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    stack := []*ListNode{}
    curNode := head
    for curNode != nil {
        stack = append(stack, curNode)
        curNode = curNode.Next
    }

    if len(stack) == n {
        return head.Next
    } else {
        stack[len(stack)-n-1].Next = stack[len(stack)-n-1].Next.Next
    }
    return head
}

如果链表有n个结点,此算法时间复杂度为O(n),空间复杂度为O(n)。

相关推荐

  1. leetcode19. 删除倒数 N

    2024-04-03 06:40:03       51 阅读
  2. Leetcode19. 删除倒数 N

    2024-04-03 06:40:03       63 阅读
  3. leetcode19. 删除倒数 N

    2024-04-03 06:40:03       42 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-03 06:40:03       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-03 06:40:03       106 阅读
  3. 在Django里面运行非项目文件

    2024-04-03 06:40:03       87 阅读
  4. Python语言-面向对象

    2024-04-03 06:40:03       97 阅读

热门阅读

  1. 利用pandas进行数据行转列和列转行

    2024-04-03 06:40:03       38 阅读
  2. Vue组件基础详细介绍

    2024-04-03 06:40:03       31 阅读
  3. 【观察者模式】

    2024-04-03 06:40:03       39 阅读
  4. 时空序列预测模型—PredRNN(Pytorch)

    2024-04-03 06:40:03       32 阅读
  5. STM32 中断应用概览

    2024-04-03 06:40:03       34 阅读