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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
image.png复杂度分析

  • 时间复杂度：O(L)，其中 L是链表的长度。

  • 空间复杂度：O(1)。

    1. //前后双指针，通法
    2. func removeNthFromEnd(head *ListNode, n int) *ListNode {
    3.   dummy := &ListNode{0, head}
    4.   first ,seconed := head, dummy    //后指针从哑结点开始，前比后多n+1步? 因为要取到目标的前一个节点才好删除！
    6.   for i :=0; i<n; i++ {
    7.       first = first.Next            //让前指针先走n步
    8.   }
    10.   for first != nil {    //前指针到终点时，后指针到-(n+1)
    11.       first = first.Next
    12.       seconed = seconed.Next        //后指针pre前进
    13.   }
    14.   seconed.Next = seconed.Next.Next    //把后指针的pre，指向tmp指针，略过cur指针，就删除完成
    16.   return dummy.Next
    17. }

    复杂度分析

  • 时间复杂度：O(L)，其中 L 是链表的长度。

  • 空间复杂度：O(L)，其中 L 是链表的长度。主要为栈的开销。
    //栈法，先进后出
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)    //把哑结点链表加入栈
  }
  pre := nodes[len(nodes)-(n+1)]    //取出cur指针的前置pre
  pre.Next = pre.Next.Next
  return dummy.Next
}