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


0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

站点统计

  • 文章总数:304 篇
  • 分类总数:19 个
  • 标签总数:189 个
  • 运行天数:864 天
  • 访问总数:475153 人次
ICP备案号: 辽ICP备20003309号