Remove Nth Node From End of List

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = head
        slow = head

        for i in range(n):
            fast = fast.next

        if not fast:
            return head.next

        while fast.next:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next
        return head

Problem Classification

Language Agnostic Coding Drills

  1. Understand a Basic Class in Python: A Python class creates a new type where objects are instances of the class. Here Solution is the class.

  2. Understanding Linked Lists: Linked lists are data structures composed of nodes, each containing a value and a reference to the next node in the list. In Python, linked lists are not built-in data structures but are fundamental to this problem.

  3. Linked List Traversal: Understanding how to traverse a linked list is crucial for this problem. This is done by setting a variable to the head node and then iteratively following the next references until you reach a node where next is None.

  4. Defining and Using Functions Within Classes (Methods): Methods are functions that are defined within a class. In this case, the method removeNthFromEnd is defined within the Solution class.

  5. The Concept of Fast and Slow Pointers: This is a common strategy used for traversing linked lists. By moving one pointer faster than the other, you can solve a variety of problems. Here, fast and slow pointers are used to identify the node to be deleted.

  6. Loops and Conditionals: Understanding how loops (like for and while loops) and conditionals (if statements) work in Python is crucial to understanding this code.

  7. Null Checking: Checking whether a variable is None is very important in linked list problems to prevent accessing next of a None object.

  8. Modifying a Linked List: Finally, this problem involves modifying the linked list by skipping over the nth node from the end, which is accomplished by adjusting the next pointer of the node before it to point to the node after it.

Targeted Drills in Python

  1. Python Class Creation

    Create a class Test and instantiate an object from it. Print a message in the constructor.

    1
2
3
4
5

    class Test:
    def __init__(self):
        print("Test class object created")

test_object = Test()

  2. Linked List Creation

    Create a simple linked list structure. Make a Node class that has an integer value and a “next” field. Then, create a LinkedList class and initialize a list with some numbers.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

    class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

ll = LinkedList()
ll.head = Node(1)
second = Node(2)
third = Node(3)
ll.head.next = second
second.next = third

  3. Linked List Traversal

    Traverse the linked list created above and print the values of each node.

    1
2
3
4

    current = ll.head
while current:
    print(current.data)
    current = current.next

  4. Defining and Using Functions Within Classes (Methods)

    Define a print_list method within the LinkedList class that does what we did in drill 3. Then call this method on an instance of LinkedList.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    class LinkedList:
    #...previous code...

    def print_list(self):
        current = self.head
        while current:
            print(current.data)
            current = current.next

ll.print_list()

  5. The Concept of Fast and Slow Pointers

    Implement a function that takes a linked list and returns the middle element of the linked list using the fast and slow pointer strategy.

    1
2
3
4
5
6
7
8

    def find_middle(ll):
    slow = fast = ll.head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.data

print(find_middle(ll))

  6. Loops and Conditionals

    Implement a function that takes a linked list and an integer n and prints the nth node in the list. You’ll need to include a conditional to check whether n is greater than the length of the list.

    1
2
3
4
5
6
7
8
9

    def print_nth_node(ll, n):
    count = 0
    current = ll.head
    while current:
        if count == n:
            print(current.data)
        count += 1
        current = current.next
print_nth_node(ll, 2)

  7. Null Checking

    Modify the function print_nth_node so that it returns “Index out of range” if n is greater than the length of the list.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    def print_nth_node(ll, n):
    count = 0
    current = ll.head
    while current:
        if count == n:
            print(current.data)
            return
        count += 1
        current = current.next
    print("Index out of range")
print_nth_node(ll, 5)

  8. Modifying a Linked List

    Implement a function that removes the nth node from the end of the list. This will involve reassigning the next pointer of the (n+1)th node from the end to the (n-1)th node from the end.

    1
2

    def remove_nth_from_end(ll, n):
    dummy =

Node(0) dummy.next = ll.head slow = fast = dummy for _ in range(n+1): fast = fast.next while fast: slow = slow.next fast = fast.next slow.next = slow.next.next ll.head = dummy.next

remove_nth_from_end(ll, 2)
ll.print_list()
```

Remember to always test your functions with different inputs to ensure they work as expected.