_19. Remove Nth Node From End of List.md

19. Remove Nth Node From End of List

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 07, 2024

Last updated : July 01, 2024

---

Related Topics : Linked List, Two Pointers

Acceptance Rate : 46.99 %

---

Solutions

• m19 v2 two-pointer.py
• m19.py
• m19 v2.c
• m19 v2.java

Python

m19 v2 two-pointer.py

# Two pointer method

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        left, right = head, head
        print(left.val, right.val)

        for i in range(n) :
            right = right.next
            
        if not right :
            return left.next

        while right.next :
            left = left.next
            right = right.next

        left.next = left.next.next

        return head

m19.py

# Mid to slow end runtime wise possibly due to the recursive stack BUT
# is consistently 84%+ on space efficiency huh


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        # output int is current index from end (starting at 1)
        def helper(currentNode: Optional[ListNode()], n: int) -> int :
            if not currentNode :
                return 1
            
            currentNo = helper(currentNode.next, n)

            if n - currentNo == -1 : # Current node = node before node to remove
                currentNode.next = currentNode.next.next
            return currentNo + 1

        # Edge cases of n == 1, len(head)
        if not head or not head.next :
            return None
        if helper(head, n) - 1 == n :
            head = head.next

        return head

C

m19 v2.c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (!head || !head->next) {
        return NULL;
    }

    struct ListNode* left = head;
    struct ListNode* right = head;

    for (int i = 0; i < n; i++) {
        right = right->next;
    }

    if (!right) {
        return head->next;
    }

    while (right->next) {
        left = left->next;
        right = right->next;
    }

    left->next = left->next->next;

    return head;
}

Java

m19 v2.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode left = head;
        ListNode right = head;
        
        
        for (int i = 0; i < n; i++) {
            right = right.next;
        }

        if (right == null) {
            return left.next;
        }

        while (right.next != null) {
            left = left.next;
            right = right.next;
        }

        left.next = left.next.next;

        return head;
    }
}