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

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

remove_ex1

示例 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int)*ListNode {
    // 遍历一次链表，记录表长Len
    if(head.Next == nil){
        return nil
    }
    Len := 1
    Head := head
    for head.Next != nil{
        head = head.Next
        Len++
    }
    // 倒数第n个结点的前驱结点在表中为第 Len - n  个结点,将其前驱节点的后继指针指向被删结点的后继指针
    head = Head
    if n == Len{
        return head.Next
    }
    for i := 1;i < Len - n;i++{
        head = head.Next
    }
    head.Next = head.Next.Next
    // 返回头结点
    return Head
}

解题思路

双指针

获取倒数第n个节点的父节点d
再根据父节点d是否为head节点，选取不同的删除方式。

题解

Ⅰ

双指针（快慢指针）

func removeNthFromEnd(head *ListNode, n int)*ListNode {
    // 双指针实现
    pre,rear := head,head
    // 快指针先走n步
    for i:=0;i < n;i++{
        if rear == nil{
            return head
        }
        rear = rear.Next
    }
    // 再快慢指针一起走，直到快指针走到尾
    if rear == nil{ // 如果快指针走到nil，则删去第一个元素
        return head.Next
    }
    for rear.Next != nil{
        pre = pre.Next
        rear = rear.Next
    }
    pre.Next = pre.Next.Next    // 删去倒数第N个结点
    return head
}

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
}

预设头结点的方法

Ⅱ

栈

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    nodes := []*ListNode{}
    dummy := &ListNode{0, head}
    for node := dummy; node != nil; node = node.Next {
        nodes = append(nodes, node)
    }
    prev := nodes[len(nodes)-1-n]
    prev.Next = prev.Next.Next
    return dummy.Next
}

预设头结点的方法

Ⅲ

递归

var a int = 0
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil{
        return nil
    }
    head.Next = removeNthFromEnd(head.Next,n)
    a++
    if a == n{
        return head.Next
    }
    return head
}

注：这个答案在测试里是完全没问题的，但作为答案可能会引发错误，原因是在答案提交的过程中包级变量好像会被省略

总结

双指针，栈及递归的熟练使用