【中等】19. 删除链表的倒数第 N 个结点
2023-12-14 20:15:27
题目
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
解题
这次两个解法是自己想到的,真不错呀。
func removeNthFromEnd(head *ListNode, n int) *ListNode {
result, tail := head, head
for i:=0;i<n;i++ {
tail = tail.Next
}
if tail == nil{
return result.Next
}
for tail.Next!=nil{
head = head.Next
tail = tail.Next
}
head.Next = head.Next.Next
return result
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
cur := head
len := 0
//先拿长度,len是链长
for ;cur!=nil; len++ {
cur = cur.Next
}
if len == n{
return head.Next
}
cur = head
for i:=1; i<len-n; i++{
cur = cur.Next
}
cur.Next = cur.Next.Next
return head
}
题解
方法一:先算链表长度
func getLength(head *ListNode) (length int) {
for ; head != nil; head = head.Next {
length++
}
return
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
length := getLength(head)
dummy := &ListNode{0, head}
cur := dummy
for i := 0; i < length-n; i++ {
cur = cur.Next
}
cur.Next = cur.Next.Next
return dummy.Next
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间:O(N)
空间:O(1)
方法二:双指针
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{0, head}
first, second := head, 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
}
作者:力扣官方题解
链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间:O(N)
空间:O(1)
哨兵节点的应用可以替代头结点的单独判断
长进
- 在对链表进行操作时,一种常用的技巧是添加一个哨兵节点(dummy node),它的 next\textit{next}next 指针指向链表的头节点。这样一来,我们就不需要对头节点进行特殊的判断了。
文章来源:https://blog.csdn.net/Miller_6/article/details/134996872
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!