3062. Winner of the Linked List Game - Week 1/5 Leetcode March Challenge
Winner of the Linked List Game - Video Solution
Watch the video solution for Winner of the Linked List Game, a easy level problem involving Linked List. This walkthrough by Programming Live with Larry has 229 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given the head of a linked list of even length containing integers.
Each odd-indexed node contains an odd integer and each even-indexed node contains an even integer.
We call each even-indexed node and its next node a pair, e.g., the nodes with indices 0 and 1 are a pair, the nodes with indices 2 and 3 are a pair, and so on.
For every pair, we compare the values of the nodes in the pair:
- If the odd-indexed node is higher, the
"Odd"team gets a point. - If the even-indexed node is higher, the
"Even"team gets a point.
Return the name of the team with the higher points, if the points are equal, return "Tie".
Example 1:
Input: head = [2,1]
Output: "Even"
Explanation: There is only one pair in this linked list and that is (2,1). Since 2 > 1, the Even team gets the point.
Hence, the answer would be "Even".
Example 2:
Input: head = [2,5,4,7,20,5]
Output: "Odd"
Explanation: There are 3 pairs in this linked list. Let's investigate each pair individually:
(2,5) -> Since 2 < 5, The Odd team gets the point.
(4,7) -> Since 4 < 7, The Odd team gets the point.
(20,5) -> Since 20 > 5, The Even team gets the point.
The Odd team earned 2 points while the Even team got 1 point and the Odd team has the higher points.
Hence, the answer would be "Odd".
Example 3:
Input: head = [4,5,2,1]
Output: "Tie"
Explanation: There are 2 pairs in this linked list. Let's investigate each pair individually:
(4,5) -> Since 4 < 5, the Odd team gets the point.
(2,1) -> Since 2 > 1, the Even team gets the point.
Both teams earned 1 point.
Hence, the answer would be "Tie".
Constraints:
- The number of nodes in the list is in the range
[2, 100]. - The number of nodes in the list is even.
1 <= Node.val <= 100- The value of each odd-indexed node is odd.
- The value of each even-indexed node is even.
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array Conversion + Pair Comparison | O(n) | O(n) | When simpler indexing logic is preferred or values must be reused later |
| Direct Linked List Simulation | O(n) | O(1) | Best general solution; single pass with constant extra memory |