3062. Winner of the Linked List Game
Problem Description
The problem provides us with a linked list where each node contains an integer. The list has an even number of nodes, and a pattern is followed where even-indexed nodes (0, 2, 4, ...) contain even integers and odd-indexed nodes (1, 3, 5, ...) contain odd integers. We can imagine these nodes as being part of 'pairs' (two adjacent nodes, starting with the head of the list). The task is to keep a score for two conceptual teams, 'Even' and 'Odd', by comparing the integer values in each pair: if the integer in the even-indexed node is higher, team 'Even' scores a point; if the integer in the odd-indexed node is higher, team 'Odd' scores a point. If both teams have the same score at the end of the list, the result is a tie. We need to return the name of the team with the higher score, or "Tie" if it's a draw.
Intuition
The essence of the solution is a straightforward simulation. We iterate through the linked list, two nodes at a time, comparing the values of each node in a pair. This is akin to a match where each pair leads to a contest, and points are awarded according to the outcome of the match (the higher value wins).
To implement this, we can maintain two variables, odd
and even
, that will serve as the score counters for the 'Odd' and 'Even' teams, respectively. Starting from the head of the list, we increment either odd
or even
depending on which node in the current pair has a larger value. Since we know the list has an even length, we are assured that we will always end on a node that is part of a complete pair. After traversing the entire list, we simply compare our two counters and return the team that accumulated the higher score or "Tie" if both scores are even.
Learn more about Linked List patterns.
Solution Approach
The given Python solution follows an iterative approach common in dealing with linked lists. It doesn't use any complex data structures or algorithms but relies on simple comparison and arithmetic operations. The core idea is to simulate the process mentioned in the problem statement using a loop. Below is a step-by-step explanation of the code:
-
Initial Score Counters: Two variables,
odd
andeven
, are initialized to zero. These variables act as score counters for the "Odd" and "Even" teams. -
Iteration Over the List: A
while
loop is used to traverse the linked list. In each iteration, the loop checks the existence of the current node and, implicitly due to the even length of the list, its next node. -
Accessing Node Values: Within each iteration, node values are accessed using
head.val
for the even-indexed node andhead.next.val
for the odd-indexed node. -
Comparing Values: For each pair, the values of the nodes (
a
andb
) are compared:- If the value of the even-indexed node (
a
) is greater than the odd-indexed node (b
), the variableeven
is incremented. - If the value of the odd-indexed node (
b
) is greater than the even-indexed node (a
), the variableodd
is incremented.
- If the value of the even-indexed node (
-
Moving to the Next Pair: The head is moved two nodes forward to the next pair by setting
head
tohead.next.next
. -
End of List: Once the algorithm has compared all pairs, and the end of the list is reached (when
head
isnull
), the loop ends. -
Determining the Winner: Finally, the function compares the accumulated scores for "Odd" and "Even":
- If
odd
is greater thaneven
, the function returns the string"Odd"
. - If
even
is greater thanodd
, it returns the string"Even"
. - If
odd
andeven
are equal, it returns the string"Tie"
.
- If
This approach has a linear time complexity of O(n), where n is the length of the linked list, since it requires a single pass through the list. The algorithm's space complexity is O(1) – irrespective of the size of the input, it only uses a fixed amount of additional memory (for the score counters and temporary variables).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a linked list with the following even-numbered nodes:
Node 1 (value 4) -> Node 2 (value 3) -> Node 3 (value 6) -> Node 4 (value 5)
Remember, the list is zero-indexed, so Node 1 is at index 0, Node 2 is at index 1, and so on.
Following the solution approach:
-
Initial Score Counters: We initialize two variables,
odd
andeven
to 0. -
Iteration Over the List: We begin from Node 1 (at index 0).
-
Accessing Node Values: Node 1 has the value
4
(even-indexed), and its next Node 2 has the value3
(odd-indexed). -
Comparing Values: Since
4
is greater than3
,even
now becomes1
, whileodd
remains at0
. -
Moving to the Next Pair: We move on to the next pair, Node 3 and Node 4.
-
Accessing Node Values: Now, Node 3 (even-indexed) has a value
6
, and Node 4 (odd-indexed) has a value5
. -
Comparing Values: Node 3's value
6
is greater than Node 4's value5
, so we incrementeven
again to2
. Theodd
score is still0
. -
Moving to the Next Pair: Since there are no more pairs, we exit the loop.
-
Determining the Winner: Comparing
odd
0
witheven
2
,even
is greater. Therefore, we return"Even"
as the winner.
In this example, the Even
team wins by a score of 2-0
. If, at any point, the team Odd
had a greater value in their respective index, we would have incremented the odd
counter instead. In a case where both teams end up with the same score, we would return "Tie"
.
Solution Implementation
1# Definition for singly-linked list.
2class ListNode:
3 def __init__(self, val=0, next=None):
4 self.val = val
5 self.next = next
6
7class Solution:
8 def gameResult(self, head: Optional[ListNode]) -> str:
9 # Initialize counters for the odd and even indexed players' points.
10 odd_points = 0
11 even_points = 0
12
13 # Traverse the linked list two nodes at a time.
14 while head and head.next:
15 # Retrieve the values of the two adjacent nodes.
16 odd_value = head.val
17 even_value = head.next.val
18
19 # Increment odd_points if the odd indexed player wins the round.
20 odd_points += odd_value < even_value
21 # Increment even_points if the even indexed player wins the round.
22 even_points += odd_value > even_value
23
24 # Move to the next pair of nodes.
25 head = head.next.next
26
27 # Determine the result based on the players' points.
28 if odd_points > even_points:
29 return "Odd"
30 elif odd_points < even_points:
31 return "Even"
32 else:
33 return "Tie"
34
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val;
6 ListNode next;
7
8 ListNode() {}
9
10 ListNode(int val) {
11 this.val = val;
12 }
13
14 ListNode(int val, ListNode next) {
15 this.val = val;
16 this.next = next;
17 }
18}
19
20class Solution {
21 public String gameResult(ListNode head) {
22 // Initialize counters for odd and even index matchups
23 int oddScore = 0;
24 int evenScore = 0;
25
26 // Traverse the linked list two nodes at a time
27 while (head != null && head.next != null) {
28 int firstValue = head.val; // Value at current node (odd index)
29 int secondValue = head.next.val; // Value at next node (even index)
30
31 // Increment the odd score if the value at odd index is less than at even index
32 oddScore += firstValue < secondValue ? 1 : 0;
33
34 // Increment the even score if the value at odd index is greater than at even index
35 evenScore += firstValue > secondValue ? 1 : 0;
36
37 // Skip to the node after the next one for the next pair
38 head = head.next.next;
39 }
40
41 // Determine the result based on scores
42 if (oddScore > evenScore) {
43 return "Odd";
44 } else if (oddScore < evenScore) {
45 return "Even";
46 } else {
47 // In case of a tie
48 return "Tie";
49 }
50 }
51}
52
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13 // Method to determine the result of the game based on odd or even indices
14 string gameResult(ListNode* head) {
15 // Initialize counters for odd and even positioned nodes
16 int oddCounter = 0, evenCounter = 0;
17
18 // Iterate over the linked list two elements at a time
19 while (head != nullptr && head->next != nullptr) {
20 // Value at the current node (odd index)
21 int currentValue = head->val;
22 // Value at the next node (even index)
23 int nextValue = head->next->val;
24
25 // Increase the odd counter if the value at the odd index is less than even index value
26 oddCounter += currentValue < nextValue;
27 // Increase the even counter if the value at the odd index is greater than even index value
28 evenCounter += currentValue > nextValue;
29
30 // Move the pointer two nodes ahead in the list
31 head = head->next->next;
32 }
33
34 // Determine the game result based on odd and even counters
35 if (oddCounter > evenCounter) {
36 return "Odd";
37 }
38 if (oddCounter < evenCounter) {
39 return "Even";
40 }
41 // If counters are equal, it's a tie
42 return "Tie";
43 }
44};
45
1/**
2 * Function to determine the game result from a linked list.
3 * The list nodes represents numbers drawn by two players, odd and even, in turns.
4 * Odd player draws on odd turns and Even player on even turns.
5 * A player scores a point if their number is greater than the other player's.
6 * Returns 'Odd' if the odd player wins, 'Even' if the even player wins, or 'Tie' if it's a draw.
7 *
8 * @param {ListNode | null} head - the head of the linked list containing game numbers.
9 * @return {string} - the result of the game: 'Odd', 'Even', or 'Tie'.
10 */
11
12function gameResult(head: ListNode | null): string {
13 // Initialize the scores for both players.
14 let oddScore = 0;
15 let evenScore = 0;
16
17 // Traverse the linked list two steps at a time.
18 while (head && head.next) {
19 // Retrieve the current two values.
20 const firstValue = head.val; // Odd player's draw.
21 const secondValue = head.next.val; // Even player's draw.
22
23 // Compare the values and update scores accordingly.
24 oddScore += firstValue > secondValue ? 1 : 0; // Odd player scores if their number is greater.
25 evenScore += firstValue < secondValue ? 1 : 0; // Even player scores if their number is greater.
26
27 // Move to the next pair of numbers.
28 head = head.next.next;
29 }
30
31 // Determine and return the result based on the scores.
32 if (oddScore > evenScore) {
33 return 'Odd';
34 } else if (oddScore < evenScore) {
35 return 'Even';
36 } else {
37 return 'Tie';
38 }
39}
40
Time and Space Complexity
The code performs a loop that iterates through the nodes of a linked list, where the step in each iteration moves two nodes forward (head
to head.next.next
). Despite this step, we still touch each node exactly once, therefore, the time complexity depends linearly on the number of nodes, resulting in O(n)
time complexity, where n
is the number of nodes in the list.
The space complexity of the algorithm is O(1)
, as there are no data structures used that grow with the input size. Only a fixed number of variables (odd
, even
, a
, b
) are used regardless of the list size.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!