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,

- Question Link β
- Possible Explanation π
- Documented C++ Code π§Ή
- 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:

- Find the length of LinkedList β L
- 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
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;
}
```

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

singlepass, we shall see that method in next post :)

## Top comments (0)