【中等】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)
哨兵节点的应用可以替代头结点的单独判断

长进

  1. 在对链表进行操作时,一种常用的技巧是添加一个哨兵节点(dummy node),它的 next\textit{next}next 指针指向链表的头节点。这样一来,我们就不需要对头节点进行特殊的判断了。

文章来源:https://blog.csdn.net/Miller_6/article/details/134996872
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。