The dummy-node technique

A dummy node (also called a sentinel) is an extra node that holds no real data and sits before the first real node. Your code works with dummy.next as the head, and at the end returns dummy.next, which is the correct head even if the original head was removed or replaced.

Most linked list bugs come from the head being special: it has no previous node, so 'delete the node after prev' does not work for it, and an empty result list has no tail to append to. A dummy gives every node, including the first, a predecessor, and gives an empty list a tail. Doubly linked lists often use two sentinels, one at each end.

1. 1Create dummy = ListNode(0, head). Now dummy.next is the real head.
2. 2Walk with a pointer that starts at dummy, not at head, and always look at cur.next. Deleting is cur.next = cur.next.next, which works even when cur.next is the real head.
3. 3When building a new list, start with tail = dummy and append with tail.next = node; tail = node. The first append is no longer a special case.
4. 4For removal from the end, place two pointers at dummy with a gap of n + 1 nodes; when the leading one reaches None, the trailing one is just before the node to remove.
5. 5Return dummy.next as the new head. Never return dummy itself or the old head variable.
6. 6In a doubly linked list, keep head and tail sentinels that always exist; every real node then has non-null prev and next, so insert and delete are four pointer updates with no checks.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)             # handles removing the real head
    slow = fast = dummy
    for _ in range(n + 1):
        fast = fast.next                  # gap of n nodes between slow and fast
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next            # slow is just before the target
    return dummy.next

def partition(head, x):
    """Nodes < x first, then nodes >= x, keeping relative order."""
    less = lt = ListNode()
    more = mt = ListNode()
    while head:
        if head.val < x:
            lt.next, lt = head, head
        else:
            mt.next, mt = head, head
        head = head.next
    mt.next = None                        # cut the old link to avoid a cycle
    lt.next = more.next
    return less.next

remove_nth_from_end works even when the head is removed, because slow can stay at the dummy. partition builds two lists behind two dummies, joins them, and sets mt.next = None so the old links cannot form a cycle. Both are O(n) time and O(1) extra space.

Cost: O(1) extra space (one node per dummy); no change to the time complexity of the algorithm.