Remove nth node from end of list Leetcode Python

by

LeetCode has a Medium coding Problem in Its’ Algorithm Section “remove nth node from end of list leetcode python”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE

remove nth node from end of list leetcode python

Question

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

Example 1:

Examples

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

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

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

Follow up: Could you do this in one pass?

Remove nth node from end of list Leetcode Python Solution

The Skeleton Code Given By Leetcode is

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """

Create two variables slow and fast, both pointing towards the head.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = head
        fast = head

Move fast Pointer n steps ahead. Like, create a loop from 0 to n. if n == number of nodes then delete the head node.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = head
        fast = head
         for i in range(0, n):
            if fast.next is None:
                # If n is equal to the number of nodes, delete the head node
                if i == n - 1:
                    head = head.next
                return head
            fast = fast.next

Now take one step at a time, slow and fast, until you reach the end. Because it is ahead, the fast pointer will undoubtedly reach the end before the slow pointer. When the fast pointer reaches the end of the list, the slow pointer will be n steps behind it, or n steps behind the list’s end. When the fast pointer reaches the end of the list, the slow pointer will be n steps behind it, or n steps behind the list’s end.

Complete Solution:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = head
        fast = head
        # Move fast pointer n steps ahead
        for i in range(0, n):
            if fast.next is None:
                # If n is equal to the number of nodes, delete the head node
                if i == n - 1:
                    head = head.next
                return head
            fast = fast.next
        # Loop until fast node reaches to the end
        # Now we will move both slow and fast pointers
        while fast.next is not None:
            slow = slow.next
            fast = fast.next
        # Delink the nth node from last
        if slow.next is not None:
            slow.next = slow.next.next
        return head

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE