LeetCode 19 in Swift: Remove Nth Node From End of List

Second edition of my LeetCode journey :)

The problem

In this problem, we need to remove the n-th node from the end of a linked list.

For example, for the list:

[1, 2, 3, 4, 5]

and n = 2, the node 4 should be removed, leaving:

[1, 2, 3, 5]

First, we need to understand the concept of a singly linked list, which appears a lot in big tech interviews.

A singly linked list is a sequence of nodes where each node contains a value, val, and a reference to the next node, next.

The problem already gives us the node class:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

The idea

The idea for the solution is to use two pointers, first and second.

Both start pointing to the head of the list.

We also use an additional pointer, previous, which always points to the node before the one that will be removed.

var first: ListNode? = head
var second: ListNode? = head
var previous: ListNode? = nil

Now we need to move the first pointer n positions ahead of second.

for _ in 0..<n {
    first = first?.next
}

After that, we move both pointers forward until first reaches the end of the list.

while first != nil {
    previous = second
    first = first?.next
    second = second?.next
}

When this loop ends, second is pointing to the node that should be removed.

To finish, we delete the desired node.

If previous is nil, it means the node to be removed is the head of the list. So the new head should be head?.next.

If that is not the case, then previous?.next is adjusted to skip second, which is the node being removed.

Complete code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */

class Solution {
    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        var first: ListNode? = head
        var second: ListNode? = head
        var previous: ListNode? = nil

        for _ in 0..<n {
            first = first?.next
        }

        while first != nil {
            previous = second
            first = first?.next
            second = second?.next
        }

        if previous == nil {
            return head?.next
        } else {
            previous?.next = second?.next
        }

        return head
    }
}

Time complexity

The time complexity is O(n).

The first pass is the for loop, which moves n steps.

The second pass is the while loop, which continues through the rest of the list.

In the worst case, the algorithm still visits the list linearly, where n is the total number of nodes in the list.

The space complexity is O(1) because we only use a few pointers.

It is a simple and efficient algorithm.

Thanks for reading!

Feel free to leave comments or suggestions :)