Swift Leetcode Series : Remove Nth Node From End of List

Swift solution in single pass (Leetcode 19)

theSwiftNerd

Remove Nth Node From End of List (Leetcode 19) -

You can also read the full story on The Swift Nerd blog with the link above.

Problem statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

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

Solution

Approach 1: Two passes

We can imagine the problem as removing the (L — n + 1)th node from the beginning. However we need to calculate the length first which will take 1 pass and in second pass we can remove the desired node (Hence Two pass approach). We also need to take care of some edge cases:

• n > Length : In this case, simple return as maximum value of n is L.
• n == length : This essentially means that we have to remove the first node of the linked list. We can simple return the next node of the head.

In the second pass, we take two pointers (current and prev) traversing adjacent to each other. The idea is have two pointers, one to the exact node and one pointer before the target node for changing the next pointers. To reach Kth node, we need to k — 1 passes from the start. If the current pointer points to the kth node, then prev pointer would be just 1 pass away to break the chain. Now simply we need to manipulate the next pointer of the prev node to remove the desired (current) node

Bonus tip!

We can optimise it further by removing the node in a single pass. Keep reading to find out 😉

Follow up: Can we do it in one pass?

Approach 2: One Pass

How can we reach the nth node from the end without calculating the length? Simple! We maintain two pointers (first and second) with a gap of n nodes in between them. When the tail node reaches the end of the linked list, the head node would be pointing to the nth node from the end. Voila!

The approach is simple but tricky. To make things simple, we would append a dummy node in the beginning of our LinkedList. This would help us to not worry about edge cases when there is only one node or removing the head of the list. The first pointer advances N + 1 steps and second node starts from the beginning of the list. Now both the nodes are exactly n nodes apart. We traverse both the nodes together till the first node reaches the end of the list. Now the second node would be just before the Nth from the end (Think about it). All we need to do is just change the next pointers. Also, remember to return the next of the dummy node!

Complexity Analysis

Time complexity : O(L) .The algorithm makes one traversal of the list of L nodes.

Space complexity : O(1). We only used constant extra space.

Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!

You can find me on TheSwiftNerd | LinkedIn | Github