LeetCode 3062 - Winner of the Linked List Game

Difficulty: 🟢 Easy
Topics: Linked List

Solution

Problem Understanding

The problem gives us the head of a singly linked list whose length is always even. The nodes are grouped into pairs based on their indices:

Nodes at indices (0, 1) form the first pair
Nodes at indices (2, 3) form the second pair
Nodes at indices (4, 5) form the third pair
And so on

Within each pair, the node at the even index belongs to the "Even" team, while the node at the odd index belongs to the "Odd" team.

For every pair, we compare the two values:

If the even-indexed node has the larger value, the "Even" team earns one point
If the odd-indexed node has the larger value, the "Odd" team earns one point

At the end, we compare the total scores:

Return "Even" if the Even team has more points
Return "Odd" if the Odd team has more points
Return "Tie" if both teams have the same number of points

The constraints are very small:

The linked list contains between 2 and 100 nodes
The length is guaranteed to be even
Node values are between 1 and 100

These constraints tell us that performance is not a major concern. Even a less efficient solution would pass comfortably. However, the problem is fundamentally simple and can be solved optimally in a single traversal of the linked list.

An important guarantee is that every even-indexed node contains an even integer and every odd-indexed node contains an odd integer. This property helps explain the team names, but it is not actually required for the algorithm itself. We only need to compare values pairwise.

The main edge cases involve:

A list with only one pair
A perfect tie between the two teams
All pairs favoring the same team

Because the list length is guaranteed to be even, we never need to worry about an incomplete pair at the end.

Approaches

Brute Force Approach

A brute-force strategy would first copy all linked list values into an array. Once the values are stored in a normal list, we can iterate through the array two elements at a time and compare adjacent values.

This works because linked lists are more cumbersome to index directly, while arrays allow easy access by position.

The process would look like this:

Traverse the linked list and store all values in an array.
Iterate through the array in steps of two.
Compare each pair.
Count points for "Even" and "Odd".
Return the final winner.

This approach is correct because every pair is examined exactly once and scored correctly.

However, it uses extra memory unnecessarily because the linked list can already be traversed sequentially. Since we only need adjacent nodes at any given time, storing the entire list is wasteful.

Optimal Approach

The key observation is that the linked list is already organized in the exact order we need. We never need random access or revisiting previous nodes.

Therefore, we can process the list directly while traversing it:

Take the current node and the next node as one pair
Compare their values
Update the appropriate score
Move forward by two nodes

This allows us to solve the problem in one pass with constant extra space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Copies all node values into an array before processing
Optimal	O(n)	O(1)	Traverses the linked list directly in pairs

Algorithm Walkthrough

Initialize two counters, even_points and odd_points, both starting at 0.
Create a pointer called current and set it to the head of the linked list. This pointer will move through the list pair by pair.
While current and current.next both exist, process one pair:

current.val represents the even-indexed node
current.next.val represents the odd-indexed node

Compare the two values:

If current.val > current.next.val, increment even_points
Otherwise, increment odd_points

The problem guarantees the values are never equal because one is always even and the other is always odd. 5. Move the pointer forward by two nodes using:

current = current.next.next

This skips to the start of the next pair. 6. After processing all pairs, compare the two scores:

Return "Even" if even_points > odd_points
Return "Odd" if odd_points > even_points
Otherwise return "Tie"

Why it works

The algorithm maintains the invariant that every processed pair contributes exactly one point to the correct team. Since the linked list is traversed pair by pair without skipping or repeating any nodes, all comparisons are handled exactly once. At the end of traversal, the score counters accurately represent the total wins for each team, so comparing them yields the correct result.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import Optional

class Solution:
    def gameResult(self, head: Optional[ListNode]) -> str:
        even_points = 0
        odd_points = 0

        current = head

        while current and current.next:
            if current.val > current.next.val:
                even_points += 1
            else:
                odd_points += 1

            current = current.next.next

        if even_points > odd_points:
            return "Even"

        if odd_points > even_points:
            return "Odd"

        return "Tie"

The implementation starts by creating counters for both teams. These counters track how many pairs each team wins.

The current pointer begins at the head of the linked list. Since the list is processed in pairs, the loop condition checks both current and current.next.

Inside the loop, the algorithm compares the values of the two nodes in the current pair. Depending on which value is larger, the appropriate score counter is incremented.

After processing a pair, the pointer advances by two nodes so that the next iteration begins at the next even-indexed node.

Finally, the two scores are compared and the correct result string is returned.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func gameResult(head *ListNode) string {
    evenPoints := 0
    oddPoints := 0

    current := head

    for current != nil && current.Next != nil {
        if current.Val > current.Next.Val {
            evenPoints++
        } else {
            oddPoints++
        }

        current = current.Next.Next
    }

    if evenPoints > oddPoints {
        return "Even"
    }

    if oddPoints > evenPoints {
        return "Odd"
    }

    return "Tie"
}

The Go implementation follows the same logic as the Python version. The main difference is pointer syntax:

current.Next is used instead of current.next
Go uses explicit variable types inferred through :=
The loop condition uses Go's for syntax rather than Python's while

No additional slices or arrays are needed, so the solution maintains constant extra space.

Worked Examples

Example 1

Input:

[2,1]

Initial state:

Pair	Even Value	Odd Value	Winner	Even Points	Odd Points
(2,1)	2	1	Even	1	0

Final comparison:

Even Points = 1
Odd Points = 0

Result:

"Even"

Example 2

Input:

[2,5,4,7,20,5]

Step-by-step traversal:

Pair	Even Value	Odd Value	Winner	Even Points	Odd Points
(2,5)	2	5	Odd	0	1
(4,7)	4	7	Odd	0	2
(20,5)	20	5	Even	1	2

Final comparison:

Even Points = 1
Odd Points = 2

Result:

"Odd"

Example 3

Input:

[4,5,2,1]

Step-by-step traversal:

Pair	Even Value	Odd Value	Winner	Even Points	Odd Points
(4,5)	4	5	Odd	0	1
(2,1)	2	1	Even	1	1

Final comparison:

Even Points = 1
Odd Points = 1

Result:

"Tie"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(1)	Only a few integer counters and pointers are used

The algorithm performs a single traversal of the linked list. Since every node participates in exactly one comparison, the runtime grows linearly with the number of nodes.

No auxiliary data structures are allocated, so the extra memory usage remains constant regardless of input size.

Test Cases

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

def build_linked_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

solution = Solution()

# Example 1, single pair where Even wins
assert solution.gameResult(build_linked_list([2, 1])) == "Even"

# Example 2, Odd wins overall
assert solution.gameResult(build_linked_list([2, 5, 4, 7, 20, 5])) == "Odd"

# Example 3, equal scores
assert solution.gameResult(build_linked_list([4, 5, 2, 1])) == "Tie"

# Smallest valid tie case
assert solution.gameResult(build_linked_list([2, 3, 8, 1])) == "Tie"

# All pairs won by Even
assert solution.gameResult(build_linked_list([10, 1, 8, 3, 6, 5])) == "Even"

# All pairs won by Odd
assert solution.gameResult(build_linked_list([2, 9, 4, 7, 6, 11])) == "Odd"

# Maximum-style values within constraints
assert solution.gameResult(build_linked_list([100, 99, 98, 97])) == "Even"

# Alternating winners ending in tie
assert solution.gameResult(build_linked_list([2, 9, 10, 1])) == "Tie"

Test	Why
`[2,1]`	Smallest valid input
`[2,5,4,7,20,5]`	Multiple pairs with Odd winning
`[4,5,2,1]`	Tie scenario
`[2,3,8,1]`	Minimal balanced tie case
`[10,1,8,3,6,5]`	Every pair favors Even
`[2,9,4,7,6,11]`	Every pair favors Odd
`[100,99,98,97]`	Tests larger values near constraints
`[2,9,10,1]`	Alternating winners

Edge Cases

Single Pair Input

The smallest possible linked list contains exactly two nodes. This is important because some implementations accidentally assume multiple iterations or mishandle loop termination.

For example:

[2,1]

The implementation handles this naturally because the loop processes one pair and then terminates after advancing two nodes.

Perfect Tie

A tie occurs when both teams win the same number of pairs. An incorrect implementation might forget to explicitly handle this case and accidentally return one of the team names.

For example:

[4,5,2,1]

The implementation correctly checks both greater-than conditions first, then returns "Tie" if neither side has more points.

All Pairs Won by One Team

Some inputs heavily favor one side. This validates that score accumulation works correctly across many iterations.

For example:

[10,1,8,3,6,5]

The implementation updates counters independently for every pair, ensuring all wins are counted properly before the final comparison.