Katkat
Back

Remove Even-Positioned Nodes from a Linked List

OracleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to manipulate singly linked list pointers in-place, specifically managing alternating node removals while maintaining correct connectivity.

Problem Statement

Given a singly linked list, remove all nodes at even-indexed positions (1-based: 2nd, 4th, 6th, etc.) and return the modified list. The operation must be performed in-place with O(1) auxiliary space, meaning you cannot create a new list or store node references in an array.

Function Signature

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

def remove_even_positioned_nodes(head: ListNode) -> ListNode:
    # Implementation here

Examples

Example 1: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 1 -> 3 -> 5 Explanation: Position 2 (val 2) and position 4 (val 4) are removed.

Example 2: Input: 10 -> 20 Output: 10 Explanation: Position 2 (val 20) is removed.

Constraints:

  • The list contains between 0 and 1,000,000 nodes.
  • Node values are integers.
  • You must not modify the values of the nodes; you must re-link the nodes themselves.

Edge Cases

  • Empty list (head is None).
  • Single-node list.
  • Lists with two nodes.

Hints

Hint 1

To remove a node from a singly linked list, you need access to the node preceding it to update its 'next' pointer.

Hint 2

Think of this as an iteration where you keep track of the 'current' odd node and skip the 'next' node by pointing the 'current.next' to 'current.next.next'.

Hint 3

Ensure your logic handles the end of the list carefully, specifically checking if 'current.next' exists before attempting to access 'current.next.next'.

Follow-up questions

  • How would you modify your algorithm if you were asked to remove all *odd-positioned* nodes instead?
  • Could you solve this problem using recursion? What would be the trade-off regarding stack space complexity?
  • How would you verify your implementation for a list with one million nodes to ensure no memory leaks occur?