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)------链表
124 0
|
4月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
26 0
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
AI助理

你好,我是AI助理

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