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

题目：

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

解题：

计算链表长度，给链表一个头节点，然后删掉第l-n个节点的下一个节点

代码：

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}


func removeNthFromEnd(head *ListNode, n int) *ListNode {
    start := &ListNode{
        Val:  0,
        Next: head,
    }
    l, i, node := 0, 0, start
    for node.Next != nil {
        node = node.Next
        l++
    }
    node = start
    for node.Next != nil {
        if i == l-n {
            if n == 1 {
                node.Next = nil
            } else {
                node.Next = node.Next.Next
            }
            break
        }
        node = node.Next
        i++
    }
    return start.Next
}

官方解答：

// 计算链表长度
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
}


// 栈
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
}


// 双指针
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
}

个人感觉栈最简单.