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
}
Last modified 7mo ago