subject

Given a linked list, please delete the penultimate node of the linked list and return the head node of the linked list.

For example:

The original linked list is converted into a list: [1, 2, 3, 4, 5], and the penultimate node needs to be deleted
The final linked list is converted into a list: [1, 2, 3, 5]

The original linked list is converted to a list: [1], and the penultimate node needs to be deleted
The final linked list is converted to a list: []

The original linked list is converted into a list: [1, 2], and the penultimate node needs to be deleted
The final linked list is converted to a list: [1]

The definition of the known linked list node and the code for the conversion between the linked list and the list are as follows:

class ListNode:  # Single linked list
    def __init__(self, val=0, next=None):
        self.val = val  # Elements stored on linked list nodes
        self.next = next  # Point to the next linked list node


def list_to_list_node(numbers):  # Convert the list into a one-way linked list and return the head node of the linked list
    dummy_head = ListNode(0)
    pre = dummy_head
    for number in numbers:
        pre.next = ListNode(number)
        pre = pre.next
    pre = dummy_head.next
    return pre


def list_node_to_list(node):  # Convert one-way linked list to list
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

Implementation idea 1

• To delete the penultimate node of the linked list, we can calculate the length of the linked list first, and then process it. Suppose the length of the linked list is 5
• If you want to delete the penultimate node of the linked list, that is, the fourth node, we only need to make the third node of the linked list point to the fifth node through next
• In one case, if the node to be deleted happens to be the head node of the linked list, this situation is not easy to handle on the original linked list, because there is no head node in front, so we uniformly set a virtual head node dummy_head and dummy_head points to the head node of the original linked list through next

Code implementation 1

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy_head = ListNode(next=head)  # Set up a virtual head node
        cur1, length = dummy_head, 0
        while cur1 is not None:  # Calculate the length of the linked list
            length += 1
            cur1 = cur1.next
        cur2, step = dummy_head, length - 1 - n  # step represents the previous position of the deleted node. Subtracting 1 is because there is an additional virtual head node
        while step:
            cur2 = cur2.next
            step -= 1
        cur2.next = cur2.next.next  # Skip the next node and point directly to the next node
        return dummy_head.next

• Time complexity: O(n)
• Space complexity: O(1)

Implementation idea 2

• It is realized by using double pointers
• Set two node pointers: slow and fast. Fast moves n bits first, and then let slow and fast move at the same time. Both stop moving until the next node pointed by fast is empty
• At this time, slow refers to the previous node in the linked list to be deleted. We only need to let the current node point to the next node through next

Code implementation 2

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy_head = ListNode(next=head)  # Set up a virtual head node
        slow, fast = dummy_head, dummy_head  # Set two node pointers
        while n:  # fast moves n steps first
            fast = fast.next
            n -= 1
        while fast.next is not None:  # slow and fast move at the same time. When fast points to an empty node, exit the loop
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next  # slow points to the next node (equivalent to skipping the next node, that is, the nth node from the bottom)
        return dummy_head.next

• Time complexity: O(n)
• Space complexity: O(1)

Implementation idea 3

• It is implemented by stack, but the space complexity will become O(n)
• Define a stack, traverse the linked list and put all nodes on the stack
• To delete the penultimate node of the linked list, you only need to let the stack perform the stack operation n times. At this time, the top of the stack is just the previous node of the node to be deleted
• Then let the top node of the stack point to the next node through next

Code implementation 3

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy_head = ListNode(next=head)  # Set up a virtual head node
        cur, stack = dummy_head, []
        while cur is not None:  # Stack all nodes
            stack.append(cur)
            cur = cur.next
        while n:  # Perform n stack operations
            stack.pop()
            n -= 1
        cur = stack[-1]  # Get the stack top element. At this time, the stack top is just the previous node of the node to be deleted
        cur.next = cur.next.next  # Skip the next node and point directly to the next node
        return dummy_head.next

• Time complexity: O(n)
• Space complexity: O(n)

More Python programming questions are waiting for you to challenge: Summary of Python programming questions (under continuous update...)