Skip to content

Linked List Front Back Pointers

Table of Contents

19. Remove Nth Node From End of List

"""
-   Given the `head` of a linked list, remove the `n-th` node from the end of the list and return its head.
"""

from typing import Optional

from leetpattern.utils import ListNode, list_from_array, list_to_array


# Linked List
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    fast, slow = dummy, dummy

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

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

    slow.next = slow.next.next

    return dummy.next


def test_removeNthFromEnd() -> None:
    head = list_from_array([1, 2, 3, 4, 5])
    assert (list_to_array(removeNthFromEnd(head, 2))) == [1, 2, 3, 5]

61. Rotate List

1721. Swapping Nodes in a Linked List

1474. Delete N Nodes After M Nodes of a Linked List 👑

from typing import Optional

from leetpattern.utils import LinkedList, ListNode


def deleteNodes(head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    cur = dummy

    while cur.next:
        for _ in range(m):
            if not cur.next:
                break
            cur = cur.next

        for _ in range(n):
            if not cur.next:
                break
            cur.next = cur.next.next

    return dummy.next


def test_deleteMiddle():
    ll = LinkedList(list(range(1, 14)))
    assert ll.to_array() == list(range(1, 14))

    ll = LinkedList(deleteNodes(ll.head, 2, 3))
    assert ll.to_array() == [1, 2, 6, 7, 11, 12]