Winner of the Linked List Game

Problem

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 thehigher points, if the points are equal, return "Tie".

Examples

Example 1:

1
2
3
4
5


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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:

1
2
3
4
5
6
7
8


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.

Solution

Method 1 – Simple Pairwise Traversal

Intuition

We traverse the linked list in pairs, comparing each even-indexed node with its next (odd-indexed) node, and tally points for “Even” and “Odd” teams. The result is based on which team has more points.

Approach

Initialize even and odd point counters to 0.
Traverse the list in steps of two:
- Compare the value of the current node (even index) and the next node (odd index).
- If even > odd, increment even points; if odd > even, increment odd points.
After traversal, return “Even”, “Odd”, or “Tie” based on the points.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    string gameResult(ListNode* head) {
        int even = 0, odd = 0;
        while (head && head->next) {
            if (head->val > head->next->val) even++;
            else if (head->val < head->next->val) odd++;
            head = head->next->next;
        }
        if (even > odd) return "Even";
        if (odd > even) return "Odd";
        return "Tie";
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


type ListNode struct {
    Val  int
    Next *ListNode
}
func gameResult(head *ListNode) string {
    even, odd := 0, 0
    for head != nil && head.Next != nil {
        if head.Val > head.Next.Val {
            even++
        } else if head.Val < head.Next.Val {
            odd++
        }
        head = head.Next.Next
    }
    if even > odd {
        return "Even"
    } else if odd > even {
        return "Odd"
    }
    return "Tie"
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class Solution {
    public String gameResult(ListNode head) {
        int even = 0, odd = 0;
        while (head != null && head.next != null) {
            if (head.val > head.next.val) even++;
            else if (head.val < head.next.val) odd++;
            head = head.next.next;
        }
        if (even > odd) return "Even";
        if (odd > even) return "Odd";
        return "Tie";
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class ListNode(var `val`: Int) {
    var next: ListNode? = null
}
class Solution {
    fun gameResult(head: ListNode?): String {
        var even = 0
        var odd = 0
        var node = head
        while (node != null && node.next != null) {
            if (node.`val` > node.next!!.`val`) even++
            else if (node.`val` < node.next!!.`val`) odd++
            node = node.next!!.next
        }
        return when {
            even > odd -> "Even"
            odd > even -> "Odd"
            else -> "Tie"
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from typing import Optional
class ListNode:
    def __init__(self, val: int = 0, next: 'Optional[ListNode]' = None):
        self.val = val
        self.next = next
class Solution:
    def gameResult(self, head: Optional[ListNode]) -> str:
        even = odd = 0
        while head and head.next:
            if head.val > head.next.val:
                even += 1
            elif head.val < head.next.val:
                odd += 1
            head = head.next.next
        if even > odd:
            return "Even"
        if odd > even:
            return "Odd"
        return "Tie"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}
impl Solution {
    pub fn game_result(mut head: Option<Box<ListNode>>) -> String {
        let mut even = 0;
        let mut odd = 0;
        while let Some(mut h) = head {
            if let Some(mut n) = h.next.take() {
                if h.val > n.val {
                    even += 1;
                } else if h.val < n.val {
                    odd += 1;
                }
                head = n.next.take();
            } else {
                break;
            }
        }
        if even > odd {
            "Even".to_string()
        } else if odd > even {
            "Odd".to_string()
        } else {
            "Tie".to_string()
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0
        this.next = next ?? null
    }
}
class Solution {
    gameResult(head: ListNode | null): string {
        let even = 0, odd = 0
        let node = head
        while (node && node.next) {
            if (node.val > node.next.val) even++
            else if (node.val < node.next.val) odd++
            node = node.next.next
        }
        if (even > odd) return "Even"
        if (odd > even) return "Odd"
        return "Tie"
    }
}

Complexity

⏰ Time complexity: O(n) — We traverse the list once, where n is the number of nodes.
🧺 Space complexity: O(1) — Only a constant amount of extra space is used.

Problem#

Examples#

Solution#

Method 1 – Simple Pairwise Traversal#

Intuition#

Approach#

Code#

Complexity#