Data Structures

Delete Nth-to-Last Node

Given the head of a linked list head and an index i, delete the ith-to-last element, and return the new head of the linked list.

The index will always be in bounds.

First Few Test Cases:

deleteNthToLastNode(ListNode.of([1, 2, 3, 4, 5]), 2)
# ListNode.of([1, 2, 3, 5])

deleteNthToLastNode(ListNode.of([1, 2, 3, 4, 5]), 5)
# ListNode.of([2, 3, 4, 5])

deleteNthToLastNode(ListNode.of([1, 2, 3, 4, 5]), 1)
# ListNode.of([1, 2, 3, 4])

To solve this problem, you have to delete the ith-to-last element:

You can solve this problem in 2 passes:

Open SpoilerClose Spoiler

To do this, you can first find the length of the linked list n, like this:

curr = head

n = 0 # the length
while curr:
    n += 1
    curr = curr.next

You can then find the index of the ith-to-last element, which is n - i. To delete that element, you can use the code from the previous problem, like this:

idx = n - i # index of ith-to-last element

# delete element using code from last problem
if idx == 0:
    return head.next
node = head
for _ in range(idx - 1): 
    node = node.next
node.next = node.next.next

Here's the solution, combining the above code:

def deleteNthToLastNode(head, i):
    curr = head
    
    # find length
    n = 0
    while curr:
        n += 1
        curr = curr.next

    # delete element
    idx = n - i
    if idx == 0:
        return head.next
    node = head
    for _ in range(idx-1): 
        node = node.next
    node.next = node.next.next

    return head

Time Complexity $O(n)$ . You loop through the list twice - first to find the length, and then to delete the element. This is O(2n) = O(n).

Space Complexity $O(1)$

You can also solve the problem in 1 pass. To do this, you can imagine that you're sliding a rod down the linked list, of size i+1.

When the rod hits the end of the list, then you are able to delete the ith-to-last element:

Here's the code for this:

def deleteNthToLastNode(head, i):
    
    L = head
    R = head

    # initialize the rod to length i + 1:
    for _ in range(i + 1):
        R = R.next

    # slide the rod down to the end
    while R:
        L = L.next
        R = R.next

    # delete L.next by setting L.next to L.next.next
    L.next = L.next.next

    return head

This code works, but it breaks when you have to remove the head of the Linked List. This is because you're assuming there will always be a node L to the left of the one you want to delete, and this isn't true in that case.

To fix this, you can add a dummy node that points to the head of the Linked List. That way you'll never be asked to delete the head; there will always be the dummy node first.

Here's the code, incorporating the dummy node idea:

# this code works even if you're asked to delete the head of the LL
def deleteNthToLastNodeWithDummyIdea(head, i):
    dummy = ListNode()
    dummy.next = head
    
    # the same exact code as above, but solved on dummy
    deleteNthToLastNode(dummy, i)

    return dummy.next

Here's the full code:

Open SpoilerClose Spoiler

def deleteNthToLastNode(head, i):
    # this dummy node lets us not worry about removing the first node
    dummy = ListNode()
    dummy.next = head
    
    # same code as before, but using dummy instead of head:
    L = dummy
    R = dummy

    # initialize the rod to length i + 1:
    for _ in range(i + 1):
        R = R.next

    # slide the rod down to the end
    while R:
        L = L.next
        R = R.next
    
    # delete L.next by setting L.next to L.next.next
    L.next = L.next.next

    return dummy.next

The dummy node idea often helps in LinkedList problems. You could have used it in the previous problem to avoid dealing with the head node deletion case too.

Time Complexity $O(n)$ . You only have 1 for-loop. You're still doing the same number of operations as before, but they happen in parallel.

Space Complexity $O(1)$

Mark as Completed:

Submits:

deleteNthToLastNode

Imports:

ListNode

Test your code to get an output here!

deleteNthToLastNode(

)

Test your code to get an output here!