Remove Nth Node From End of List

Photo by C D-X on Unsplash

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

Example 1:

example
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

Algorithm -

A one pass solution can be done using two pointers. Move one pointer fastn+1 places forward, to maintain a gap of n between the two pointers and then move both at the same speed. Finally, when the fast pointer reaches the end, the slow pointer will be n+1 places behind — just the right spot for it to be able to delete the next node.

Added comments for each step in the code, please do one pass tracing using pen and paper for better understanding.

Complexity- Both time and space is O(n).

--

--

--

Full Stack Programmer, love to solve problem’s during free time.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Peak element Intuition

Where cloud storage is headed in the future

Smag Grotto — TryHackMe, WriteUp

Creating a Graphite Cluster on Kubernetes

Attaching pi4 camera module and usb webcam for photo and v

0x00 Basics of Reverse Engineering: Stack

Computer Networking : Types of Networks and Devices

SDLC (Software Development Life Cycle)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jaydeep

Jaydeep

Full Stack Programmer, love to solve problem’s during free time.

More from Medium

Chain Of Responsibility Design Pattern

Singleton Design Pattern

SOLID PRINCIPLES

Decorator Pattern