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

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

19.删除链表的倒数第N个结点

19.删除链表的倒数第N个结点

题解

思路:

1.计算链表长度

1.计算链表长度
2.增加一个哑节点,遍历到倒数n+1的位置

2.栈存储节点

1.存储所有节点
2.倒数n+1的节点就是nodes[len(nodes)-1-n]

3.双指针

1.两个指针,步伐相同
2.快指针先移动n步
3.两个指针一起移动,直到快指针为nil
4.此时慢指针就是倒数n位置

代码

func removeNthFromEnd(head *ListNode, n int) *ListNode {
  //计算链表长度
  length := getLength(head)
  dummy := &ListNode{
    Val:  0,
    Next: head,
  }
  cur := dummy
  //遍历到倒数n+1的位置
  for i := 0; i < length-n; i++ {
    cur = cur.Next
  }
  //去除倒数n
  cur.Next = cur.Next.Next
  return dummy.Next
}
func getLength(head *ListNode) (ans int) {
  for head != nil {
    ans++
    head = head.Next
  }
  return ans
}


func removeNthFromEnd(head *ListNode, n int) *ListNode {
  var nodes []*ListNode
  dummy := &ListNode{
    Val:  0,
    Next: head,
  }
  //存储所有节点
  for node := dummy; node != nil; node = node.Next {
    nodes = append(nodes, node)
  }
  //找出倒数n+1的节点
  prev := nodes[len(nodes)-1-n]
  prev.Next = prev.Next.Next
  return dummy.Next
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
  dummy := &ListNode{
    Val:  0,
    Next: head,
  }
  first := head
  second := dummy
  for i := 0; i < n; i++ {
    first = first.Next
  }
  for first != nil {
    first = first.Next
    second = second.Next
  }
  second.Next = second.Next.Next
  return dummy.Next
}


目录
打赏
0
0
0
0
9
分享
相关文章
|
4月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
54 1
|
4月前
|
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
100 1
链表的中间结点
【10月更文挑战第24天】链表的中间结点是链表操作中的一个重要概念,通过快慢指针法等方法可以高效地找到它。中间结点在数据分割、平衡检测、算法应用等方面都有着重要的意义。在实际编程中,理解和掌握寻找中间结点的方法对于解决链表相关问题具有重要价值。
35 1
|
4月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
57 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
4月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
68 0
|
4月前
|
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
125 0
|
4月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
26 0
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
6月前
|
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
78 6
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
151 2
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等