题目

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

示例 1：输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：输入：head = [1], n = 1 输出：[]

示例 3：输入：head = [1,2], n = 1 输出：[1]

提示：链表中结点的数目为 sz

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

进阶：能尝试使用一趟扫描实现吗？

注意：本题与主站 19 题相同

解题思路分析

1、遍历；时间复杂度O(n)，空间复杂度O(1)

func removeNthFromEnd(head *ListNode, n int) *ListNode {
   temp := &ListNode{Next: head}
   cur := temp
   total := 0
   for cur.Next != nil {
      cur = cur.Next
      total++
   }
   cur = temp
   count := 0
   for cur.Next != nil {
      if total-n == count {
         cur.Next = cur.Next.Next
         break
      }
      cur = cur.Next
      count++
   }
   return temp.Next
}

2、快慢指针；时间复杂度O(n)，空间复杂度O(1)

func removeNthFromEnd(head *ListNode, n int) *ListNode {
   temp := &ListNode{Next: head}
   fast, slow := temp, temp
   for i := 0; i < n; i++ {
      fast = fast.Next
   }
   for fast.Next != nil {
      fast = fast.Next
      slow = slow.Next
   }
   slow.Next = slow.Next.Next
   return temp.Next
}

3、递归；时间复杂度O(n)，空间复杂度O(n)

var count int

func removeNthFromEnd(head *ListNode, n int) *ListNode {
   if head == nil {
      count = 0
      return nil
   }
   head.Next = removeNthFromEnd(head.Next, n)
   count = count + 1
   if count == n {
      return head.Next
   }
   return head
}

总结

Medium题目，题目同leetcode 19.删除链表的倒数第N个节点