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       19 阅读
  2. Leetcode19. 删除倒数 N

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

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

最近更新

  1. leetcode705-Design HashSet

    2024-04-03 06:40:03       5 阅读
  2. Unity发布webgl之后打开streamingAssets中的html文件

    2024-04-03 06:40:03       5 阅读
  3. vue3、vue2中nextTick源码解析

    2024-04-03 06:40:03       6 阅读
  4. 高级IO——React服务器简单实现

    2024-04-03 06:40:03       5 阅读
  5. 将图片数据转换为张量(Go并发处理)

    2024-04-03 06:40:03       4 阅读
  6. go第三方库go.uber.org介绍

    2024-04-03 06:40:03       6 阅读
  7. 前后端AES对称加密 前端TS 后端Go

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

热门阅读

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

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

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

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

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

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