# Remove nth Node from Last - Leet Code Solution

September 11, 2019

## Problem Statement

Given a linked list, remove the n-th node from the end of list and return its head.

## Solution

There can be many solution for this. Lets start with a brute force simple solution.

### Algorithm-1

You can simply iterate full link list, and count its length. Lets say it: L Calculate L-n. And, move pointer from head to this many times. This node will be the one who has to be deleted.

This requires 2 iteration. Although complexity is still O(n). But, we can think of more optimized version of this algorithm.

### Algorithm-2

We can leverage two pointer concept. Where one pointer moves ahead of first pointer. We just need to keep a distance of ‘n’ between two pointers.

• Keep p1 at head, move p2 ahead one step at a time.
• Move p2 n times.
• Now, difference between p1 and p2 is ‘n’
• We now have to move both the pointers ahead with same speed. i.e. one step at a time.
• When 2nd pointer reaches end of link list, the first pointer will be at the desired node that we want to delete.

Lets look at the code:

``````public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode prev = null;

for (int i=0; i<n; i++) {
fast = fast.next;
}
while (fast != null) {
prev = h;
h = h.next;
fast = fast.next;
}
if (prev == null) {
//special condition where first pointer is at the head only. And, we want to delete head
}

prev.next = h.next;
}``````

Above code does assume that length of list is always greater than equal to ‘n’.

## Performance

BTW, this code submission to leetcode turns out to be the fastest.

``````Runtime: 0 ms, faster than 100.00% of Java online submissions for Remove Nth Node From End of List.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Remove Nth Node From End of List.``````

## Similar Posts

### Maximum Length of Subarray With Positive Product - Leet Code Solution

Problem Statement Maximum Length of Subarray With Positive Product. Given an…

### Check whether an integer number given is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

### Three Sum - Leet Code Solution

Problem Statement Given an array nums of n integers, are there elements a, b, c…

### Longest Substring without repeating characters - Leet Code Solution

Problem Statement Given a string, find the length of the longest substring…

### What is Heap Data Structure

Its a tree based data structure which is a complete binary tree(all nodes have…

### Valid Anagrams - Leet Code Solution

Problem Statement Given two strings s and t , write a function to determine if t…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…