3062. Winner of the Linked List Game

EasyLinked List
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

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:

  1. Initial Score Counters: Two variables, odd and even, are initialized to zero. These variables act as score counters for the "Odd" and "Even" teams.

  2. 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.

  3. Accessing Node Values: Within each iteration, node values are accessed using head.val for the even-indexed node and head.next.val for the odd-indexed node.

  4. Comparing Values: For each pair, the values of the nodes (a and b) are compared:

    • If the value of the even-indexed node (a) is greater than the odd-indexed node (b), the variable even is incremented.
    • If the value of the odd-indexed node (b) is greater than the even-indexed node (a), the variable odd is incremented.

  5. Moving to the Next Pair: The head is moved two nodes forward to the next pair by setting head to head.next.next.

  6. End of List: Once the algorithm has compared all pairs, and the end of the list is reached (when head is null), the loop ends.

  7. Determining the Winner: Finally, the function compares the accumulated scores for "Odd" and "Even":

    • If odd is greater than even, the function returns the string "Odd".
    • If even is greater than odd, it returns the string "Even".
    • If odd and even are equal, it returns the string "Tie".

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).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Example 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:

  1. Initial Score Counters: We initialize two variables, odd and even to 0.

  2. Iteration Over the List: We begin from Node 1 (at index 0).

  3. Accessing Node Values: Node 1 has the value 4 (even-indexed), and its next Node 2 has the value 3 (odd-indexed).

  4. Comparing Values: Since 4 is greater than 3, even now becomes 1, while odd remains at 0.

  5. Moving to the Next Pair: We move on to the next pair, Node 3 and Node 4.

  6. Accessing Node Values: Now, Node 3 (even-indexed) has a value 6, and Node 4 (odd-indexed) has a value 5.

  7. Comparing Values: Node 3's value 6 is greater than Node 4's value 5, so we increment even again to 2. The odd score is still 0.

  8. Moving to the Next Pair: Since there are no more pairs, we exit the loop.

  9. Determining the Winner: Comparing odd 0 with even 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
Not Sure What to Study? Take the 2-min Quiz：

How does quick sort divide the problem into subproblems?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Recommended Readings

Linked List Cycle

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫