Winner of the Linked List Game - Solution & Explanation

Problem Overview: You are given the head of a linked list with an even number of nodes. Nodes are compared in pairs: the first node against the second, the third against the fourth, and so on. If the first node in a pair has a larger value, Alice scores a point. If the second node is larger, Bob scores. After processing the entire list, return the player with the higher score or "Tie" if both scores are equal.

Approach 1: Convert Linked List to Array (Simulation) (Time: O(n), Space: O(n))

A straightforward approach is to first copy all node values into an array. Once the values are in a contiguous structure, iterate through the array in steps of two and compare arr[i] with arr[i+1]. Increment Alice's score if the first value is larger, otherwise increment Bob's score when the second value is larger. This approach simplifies traversal logic because random access is available, but it uses extra memory proportional to the number of nodes.

This method is useful when you prefer simpler indexing logic or when the linked list values are needed for additional processing. However, the extra array allocation makes it less optimal compared to operating directly on the linked list.

Approach 2: Direct Linked List Simulation (Time: O(n), Space: O(1))

The optimal solution processes the list directly without extra storage. Use a pointer to traverse the linked list two nodes at a time. For each pair, compare current.val and current.next.val. If the first value is greater, increment Alice's score; if the second is greater, increment Bob's score. Then advance the pointer by two nodes and repeat until the list ends.

This works because the game rules naturally align with pairwise traversal. Each iteration performs constant work: a comparison, a score update, and a pointer jump. The entire list is scanned exactly once, giving O(n) time complexity while maintaining O(1) auxiliary space.

This is essentially a simple simulation over a linked structure. The main detail to watch is pointer movement—always advance by two nodes so each pair is processed exactly once.

Recommended for interviews: The direct linked list simulation is the expected solution. It demonstrates that you can traverse a linked structure efficiently without unnecessary memory allocations. Mentioning the array-based simulation first can show basic reasoning, but implementing the single-pass pointer traversal proves stronger understanding of linked list manipulation and space optimization.