19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output:
[1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output:
[]
Example 3:
Input: head = [1,2], n = 1
Output:
[1]
Constraints:
  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz
Follow up: Could you do this in one pass?

解題

這題我使用了兩個指針,第一個指針first抵達終點時,第二個指針second指向應該被刪除的節點前一個節點。並另外處理刪除節點位於第一個和最後一個的特殊情況。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
if head.Next==nil {
return nil
}
size := 1
first, second:= head, head
for first.Next!=nil && second.Next!= nil {
first = first.Next
if size>n {
second = second.Next
}
size++
}
if size==n {
return head.Next
}
if n==1 {
second.Next = nil
return head
}
second.Next = second.Next.Next
return head
}