LinkedList Questions: [Single Pass] Delete nth node from end
Tags: algorithms, programming, codenewbie, linkedlist
Published: 2021-06-30 22:25:23

In this series of posts, I will discuss coding questions on the `LinkedList` Data structure.
The posts in this series will be organized in the following way,

1. Question Link ❓
2. Possible Explanation 📝
3. Documented C++ Code 🧹
4. Time and Space Complexity Analysis ⌛🌌

## The Question

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

**Constraints:**

- The number of nodes in the list is `sz`.
- `1 <= sz <= 30`
- `0 <= Node.val <= 100`
- `1 <= n <= sz`

[https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/](https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/)

> 💡 Give yourself atleast 15-20 mins to figure out the solution :)

## Approach 2: Single Pass

### What do I mean by single pass here?

If you recall in the last post, we travelled the list two times:

{% post https://dev.to/kathanvakharia/likedlist-questions-delete-nth-node-from-end-in-two-pass-2j63 %}

1. To calculate the length of list.
2. To delete the `L - n + 1` th node where `L` is the length of list.

That's the reason we called it two pass method. 

But in this approach, we will travel the list only one time i.e. every node will be travelled *exactly once*. 

### Building Blocks

Before we begin our discussion, I would like you to be aware of few observations when traversing a linkedlist. 

- If you travel `m` distance from the start, you'll end being on the `m + 1` th node.
- If you append a dummy node( `start` ) at the start of linkedlist, we can reach the `m`th node in *original* linkedlist in `m` steps from `start`. ( 1 step means `cur = cur→next` operation )

### The Approach

> 📓 This approach might look a bit complicated but believe me, it is VERY important to understand it as this method forms the basis of many other questions( important ones ) on linkedlist.

*Inorder to understand images, consider L=6( ListLength ) and n=3( postion of node from end that is to be deleted ).*

The idea is still the same, we would want to delete the `L - n + 1` th node from the beginning.

Here's what we will do, 

1) Create a dummy node `start`  and make it' s `next` equal to `head`. 
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5oa0xix5gg556txtojn4.png)
 
2) Initialize two pointers `fast` and `slow` equal to  `start` node i.e their `next` is equal to `head` .
3) Make `fast` point to the `n`th node in original linkedlist by peforming `n` iterations( steps ).
     🎯 Now hold on and think, how much steps will it take for  `fast`  to reach the last node?
     🎯 We are at the `n`th node from start, so after `L - n` steps we will reach the last node. [**IMP**]
![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xjkg8a8tjoacaihgj100.png)
 
4) Move `fast` and `slow` simultaneouly *one* step at a time untill `fast` reaches the *last* node. This will ensure both pointers perform `L - n`  steps.
     🎯 This will ensure, now `slow` points to the `L - n` th node. ( [Point 2](#building-blocks) of buldingblocks )
5) Delete the required node( `slow → next` ) using `slow` pointer.

![image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l3ax1o5elnuyvvbfrobr.png)
 
## C++ Code

### Definition of LinkedList

```cpp
//Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

```

### Solution

```cpp
ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        //! list is never empty

        //- initializing pointers
        ListNode *start = new ListNode();
        start->next = head;
        ListNode *fast = start;
        ListNode *slow = start;

        //make fast point to the nth node
        for (int i = 1; i <= n; i++)
        {
            fast = fast->next;
        }

        //move "slow" ahead untill "fast" points to the last node
        //i.e point "slow" to one node preceding the required node
        while (fast->next != nullptr)
        {
            fast = fast->next;
            slow = slow->next;
        }

        //deleting the nth node from end or n-k+1th node from begin
        ListNode *t = slow->next;
        slow->next = slow->next->next;
        delete t;

        return start->next;
    }
```

## Complexity Analysis

`L` is the length of linkedlist here

### Time Complexity: O(L)

We have travelled the list exactly once.

### Space Complexity: O(1)

We didn't use any extra space.