Skip to main content

Leetcode 19: Remove Nth Node From End of List

 

1. Problem Statement (Simple Explanation):


You are given the head of a singly linked list and an integer n.

You must remove the n-th node from the end of the list, and return the (possibly new) head.

  • The list has at least 1 node.

  • 1 <= n <= size of list.


2. Examples:


Example 1:

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

The 2nd node from the end is 4 (nodes from end: 5(1st), 4(2nd)).

Output: [1,2,3,5]



Example 2:

Input: head = [1], n = 1

The 1st node from the end is 1 itself.

Output: []


Example 3:

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

The 1st node from the end is 2.

Output: [1]


Constraints:

  • 1 <= sz <= 30

  • 0 <= Node.val <= 1000

  • 1 <= n <= sz

Follow-up: Can you do it in one pass?


3. Approach 1 – Two-pass (Count then Remove) – Simple but Two Passes:


Idea:

  1. First pass: compute the length L of the list.

  2. The node to remove is at position L - n (0-based) or L - n + 1 (1-based) from the start.

  3. Second pass: walk to the node just before the node to delete and adjust pointers.

This is easy but requires two passes over the list.


Pseudo-code (Two-pass):



Time: O(L)(two passes but still linear).
Space: O(1).


4. Approach 2 – One-pass Two-pointer Technique (Fast/Slow) – Optimal:


This is the standard solution for the follow-up.


Intuition:


Use two pointers:

  • fast

  • slow

Steps:

  1. Move fast pointer n steps ahead.

  2. Then move both fast and slow together until fast reaches the end.

  3. At that point, slow will be just before the node to delete.

  4. Adjust slow.next to skip the target node.

To handle removing the head (when the removed node is the first), use a dummy node before head.


Algorithm (Step-by-Step):


  1. Create a dummy node:

    • dummy.next = head

    • Both fast and slow start at dummy.

  2. Move fast ahead n + 1 steps (so that the gap between fast and slow remains n nodes and slow lands just before the node to delete).

    • Alternatively, move fast n steps from head while slow starts from dummy; equivalent variants exist. A common pattern is:

      • Move fast n steps starting from dummy.next.

      • Then move both until fast.next == null.

      • We’ll use a clear variant: move fast n steps from the head, starting fast = head, slow = dummy.

  1. Then move both pointers one step at a time:

    • While fast is not null:

      • fast = fast.next

      • slow = slow.next

  2. After the loop, slow.next is the node to be removed.

  3. Remove it:

    • slow.next = slow.next.next

  4. Return dummy.next.


Pseudo-code (One-pass, clear variant):



Complexity:


Let L be the length of the list:

  • Time: O(L)

  • Space: O(1)


5. Java code:



6. C code:



7. C++ code:



8. Python code:



9. JavaScript code:



Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more