leetcode-删除链表的倒数第N个节点

题目
给你一个链表，删除链表的倒数第n个节点，并且返回链表的头节点。(考虑使用一次扫描）

分析

1. 如何知道是倒数第n个节点，如果第n个节点知道了，第n-1和第n+1节点也就知道了，那么删除就好做了。
2. 返回链表头节点，如果倒数第n个节点刚好是头节点，删除后，需返回头节点的下一个节点，如果不是头节点，则直接返回原链表头节点。

可能思路

• 方法一 - 正序遍历
  由于链表只能顺序遍历才能确定序号，所以我们需要先获取链表的长度，获取到链表长度len后，倒数第n个节点，也就是顺数第len-n+1个节点，此时删除第len-n+1个节点，并返回原链表的头节点，就算完成了。代码实现如下：

func getListNodeLength(l *ListNode) int {
    var length int
    for l != nil {
        l = l.Next
        length++
    }
    return length
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getListNodeLength(head)
    cur := head 
    for i:=0; i < length - n; i ++ {
        cur = cur.Next
    }    
    cur.Next = cur.Next.Next
    return head
}

提交测试,无法通过。

0/208 cases passed (N/A)

分析代码，cur代表当前节点，遍历到length -n -1 时，刚好是倒数第N个节点，但是我们需要删除的时第N个节点，此时我们是无法删除当前节点的，只有当我们遍历到第N个节点的上一个节点时，才能删除第N个节点，于是修改如下：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getListNodeLength(head)
    cur := head 
    for i:=0; i < length - n -1; i ++ {
        cur = cur.Next
    }    
    cur.Next = cur.Next.Next
    return head
}

提交测试,报错空指针，

1/208 cases passed (N/A)
Error
Line 30: panic: runtime error: invalid memory address or nil pointer dereference
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x8 pc=0x4b2373]
main.removeNthFromEnd(...)
solution.go, line 30
main.__helper__(...)
solution.go, line 37
main.main()
solution.go, line 76
Testcase
[1]
1
Expected Answer
[]

当链表长度为1的情况需要单独讨论。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getListNodeLength(head)
    if length <= 1 {
        return nil
    }
    cur := head 
    for i:=0; i < length - n -1; i ++ {
        cur = cur.Next
    }    
    cur.Next = cur.Next.Next
    return head
}

提交测试，依旧无法通过所有case.

190/208 cases passed (N/A)
Testcase
[1,2]
2
Answer
[1]
Expected Answer
[2]

原因是，当n等于数组长度时，我们无法遍历，也就是头节点就是我们要删除的节点，同样这种情况也需要另外处理。修改代码如下：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getListNodeLength(head)
    if length <= 1 {
        return nil
    }
    if length == n {
        return head.Next
    }
    cur := head
    for i := 1; i < length-n; i++ {
        cur = cur.Next
    }
    cur.Next = cur.Next.Next
    return head
}

提交测试，通过。

208/208 cases passed (1 ms)
Your runtime beats 32.03 % of golang submissions
Your memory usage beats 13.75 % of golang submissions (2.2 MB)

再思考以下，上面的代码中链表长度为1和链表长度等于n两种情况需要单独讨论，那有没有方法能把这两种情况概括进去呢？
首先长度为1，按照题目要求，n只能为1，所以两种情况等同于一种情况。那就是说我们只需要考虑倒数第N个节点刚好时头节点时，如何去遍历。
很显然，假设我们要遍历，那么头节点前面必定还有一个节点，这样才能进行遍历，那么我们可以构造这个节点，官方的说法是叫“哑节点”，这个“哑节点”指向我们的当前链表。于是代码可以修改如下：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    length := getListNodeLength(head)
    dummy := &ListNode{Val: 0, Next: head}
    cur := dummy
        // 循环遍历到前两位的位置就是对应的倒数第N的位置
    for i := 0; i < length-n; i++ {
        cur = cur.Next
    }
    cur.Next = cur.Next.Next
    return dummy.Next
}

至此，整个代码非常的简洁明了。

• 方法二 - 栈
  栈，我们知道是先进后出的，当我们把所有节点入栈后，然后顺序的获取栈的第N个节点并删除，一样可以实现。代码如下：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    // 定义栈，这里我们使用数组
    var stack = make([]*ListNode, 0)
    // 将节点入栈
    for node := dummy; node != nil; node = node.Next {
        stack = append(stack, node)
    }
    //获取第N个节点的前一个节点
    prev := stack[len(stack)-n-1]
        // 删除第N个节点
    prev.Next = prev.Next.Next
    return dummy.Next
}

两种方法时间复杂度都是O(N),N为数组长度，空间复杂度，方法一是O(1)，方法二是O(N)