FastPrep
Problem · Linked List

Remove Even-Positioned Linked-List Nodes

Learn this problem
● EasyOracle logoOracleFULLTIMEPHONE SCREEN

Problem statement

Given the head of a finite, acyclic singly linked list, remove every node whose one-based position in the original list is even and return the resulting head.

Keep the nodes originally at positions 1, 3, 5, ... in their original relative order. Relink the existing nodes; do not change any node value. The input list may be empty, in which case return an empty list.

Function

removeEvenPositionedNodes(head: ListNode) → ListNode

Examples

Example 1

head = [1,2,3,4,5]return = [1,3,5]

The nodes originally at positions 2 and 4 are removed.

Example 2

head = [7,8]return = [7]

The second node is in an even position, so only the first node remains.

Example 3

head = []return = []

An empty list remains empty.

Constraints

  • 0 <= number of nodes <= 100000.
  • Every node value fits a signed 32-bit integer.
  • The input list is finite and contains no cycle.
  • Reuse the existing nodes and use O(1) auxiliary space.

More Oracle problems

drafts saved locally
/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode next;
 * }
 */
public ListNode removeEvenPositionedNodes(ListNode head) {
    // TODO: keep only nodes from odd one-based positions.
}
head[1,2,3,4,5]
expected[1,3,5]
checking account