Welcome to Subscribe On Youtube
3062. Winner of the Linked List Game
Description
You are given the head
of a linked list of even length containing integers.
Each oddindexed node contains an odd integer and each evenindexed node contains an even integer.
We call each evenindexed 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 oddindexed node is higher, the
"Odd"
team gets a point.  If the evenindexed 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 oddindexed node is odd.
 The value of each evenindexed node is even.
Solutions
Solution 1: Simulation
Traverse the linked list, each time taking out two nodes, compare their values, and then update the scores of odd and even numbers based on the comparison results. Finally, compare the scores of odd and even numbers and return the result.
The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $O(1)$.

/** * Definition for singlylinked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public String gameResult(ListNode head) { int odd = 0, even = 0; for (; head != null; head = head.next.next) { int a = head.val; int b = head.next.val; odd += a < b ? 1 : 0; even += a > b ? 1 : 0; } if (odd > even) { return "Odd"; } if (odd < even) { return "Even"; } return "Tie"; } }

/** * Definition for singlylinked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: string gameResult(ListNode* head) { int odd = 0, even = 0; for (; head != nullptr; head = head>next>next) { int a = head>val; int b = head>next>val; odd += a < b; even += a > b; } if (odd > even) { return "Odd"; } if (odd < even) { return "Even"; } return "Tie"; } };

# Definition for singlylinked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def gameResult(self, head: Optional[ListNode]) > str: odd = even = 0 while head: a = head.val b = head.next.val odd += a < b even += a > b head = head.next.next if odd > even: return "Odd" if odd < even: return "Even" return "Tie"

/** * Definition for singlylinked list. * type ListNode struct { * Val int * Next *ListNode * } */ func gameResult(head *ListNode) string { var odd, even int for ; head != nil; head = head.Next.Next { a, b := head.Val, head.Next.Val if a < b { odd++ } if a > b { even++ } } if odd > even { return "Odd" } if odd < even { return "Even" } return "Tie" }

/** * Definition for singlylinked list. * class ListNode { * val: number * next: ListNode  null * constructor(val?: number, next?: ListNode  null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function gameResult(head: ListNode  null): string { let [odd, even] = [0, 0]; for (; head; head = head.next.next) { const [a, b] = [head.val, head.next.val]; odd += a < b ? 1 : 0; even += a > b ? 1 : 0; } if (odd > even) { return 'Odd'; } if (odd < even) { return 'Even'; } return 'Tie'; }