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
}