DEV Community

Cover image for LinkedList Questions: [Two Pass] Delete nth node from end
Kathan Vakharia
Kathan Vakharia

Posted on β€’ Edited on

3 2

LinkedList Questions: [Two 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 :)

There are two approaches possible, in this post we will see the first one.

Approach 1: Two Pass

If you think a bit, nth node from end is list_len - n + 1 th node from beginning.

image

So our algorithm is:

  1. Find the length of LinkedList β†’ L
  2. Delete the (L - n + 1)th node from beginning.

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) {}
};

Enter fullscreen mode Exit fullscreen mode

Solution

ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        //- if LL is empty
        if (!head)
            return head;

        //note: first pass : O(n)
        //- getting length of LL 
        int cnt = 0;
        ListNode *temp = head;
        while (temp)
        {
            cnt++;
            temp = temp->next;
        }

        //* Standard Procedure to delete (k+1)th node from beginning

        //note: Required Node: (cnt - n +1)th node
        //note: we have to go "cnt-n" times deep to stand at required node
        int k = cnt - n;
        ListNode *cur = head;
        ListNode *prev = nullptr; //it will point one node preceding to cur

        //note: second pass :O(n)
        while (k > 0)
        {
            prev = cur;
            cur = cur->next;
            k--;
        }

        //- first node of the LL is to be deleted
        if (!prev)
        {
            temp = cur;
            cur = cur->next;
            delete temp;
            head = cur; //! cur is the new head
        }
        else
        {
            prev->next = cur->next;
            delete cur;
        }
        return head;
    }
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

N is the length of LinkedList.
K is the postion of node from end.

Time Complexity: O(N)

image

Space Complexity: O(1)

We didn't use any extra space.

πŸ’‘ It turns out there's a better method to solve this question in single pass, we shall see that method in next post :)

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (0)

Image of Docusign

πŸ› οΈ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more