## DEV Community 👩‍💻👨‍💻 is a community of 916,270 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Kathan Vakharia

Posted on • Updated on

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

``````

### Solution

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

//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;
}
}
``````

## Complexity Analysis

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

### Time Complexity: O(N) ### 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 :)

## Top comments (0)

#### 🌱 DEV runs on 100% open source code known as Forem.

Contribute to the codebase or learn how to host your own.