leetcode19
题目要求返回头结点

• 方法一：这是我的第一个想法，也是最笨的想法
  一次完全遍历， 一次不完全遍历，第二次删除元素，用了一个虚拟头结点， 第一次遍历来获取完整链表长度，由于单链表不能双向遍历，所以再第二次遍历length-n次，然后进行删除
  code:

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummyhead := &ListNode{}
    dummyhead.Next = head
    node := dummyhead.Next
    length := 0
    for node!=nil{
        node = node.Next
        length++
    }
    if n>length{
        return dummyhead.Next
    }
    if n==length{
        dummyhead.Next = dummyhead.Next.Next
        return dummyhead.Next
    }
    readyto_delete := length - n
    // 这里容易错， 必须要吧node归位
    node = dummyhead.Next
    for node.Next!=nil&&readyto_delete>1{
        readyto_delete --
        node = node.Next
    }
    fmt.Println("node:", node.Val, "length:", length)
    // node.Next = node.Next.Next
    if node.Next!=nil{
        node.Next = node.Next.Next
    }else{
        fmt.Println("000")
    }
    return dummyhead.Next
}

• 方法二：
  利用了双指针法和虚拟头结点
  快慢指针加虚拟节点，快指针先一次走n+1个长度，然后两个指针同步走，快指针为nil的时候则，慢指针指向的是要删除节点的上一个节点。

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{}
    dummy.Next = head
    fast := dummy
    slow := dummy
    n = n+1
    for n>0{
        n--
        fast = fast.Next
    }
    for fast!=nil{
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    // fmt.Println(fast.Val)
    return dummy.Next
}

反向：

    for n>0{
        n--
        fast = fast.Next
    }

正向：

    for i:=0;i<n;i++{
        fast = fast.Next
    }

这里我总结了一下，里面遍历的次数要为n+1