LinkedList Questions: [Single Pass] Delete nth node from end

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/

💡 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:

LinkedList Questions: [Two Pass] Delete nth node from end

Kathan Vakharia ・ Jun 28 '21 ・ 2 min read

#algorithms #programming #codenewbie #linkedlist

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 mth 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.

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 nth 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 nth node from start, so after L - n steps we will reach the last node. [IMP]

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 of buldingblocks )
5) Delete the required node( slow → next ) using slow pointer.

C++ Code

Definition of LinkedList

//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

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.