We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Winner of the Linked List Game

Number: 3368

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

You are given the head of a linked list of even length where each odd-indexed node contains an odd integer and each even-indexed node contains an even integer. Define each pair as two consecutive nodes (i.e., node at index 0 with index 1, index 2 with index 3, etc.). For every pair, if the odd-indexed node’s value is greater than the even-indexed node’s value, the "Odd" team earns a point; otherwise, if the even-indexed node’s value is higher, the "Even" team receives a point. Return the team name with the higher points. If both teams have the same number of points, return "Tie".

Key Insights

  • The list length is even, ensuring every node has a partner.
  • The head of the list is at index 0 (even-indexed node) and its next node is at index 1 (odd-indexed node).
  • Compare each pair: first node (even-indexed) vs. second node (odd-indexed).
  • Tally points for "Odd" team if the second node is greater, otherwise for "Even" team.
  • Return "Tie" if both teams tie.

Space and Time Complexity

Time Complexity: O(n) since we process each pair in one pass through the linked list. Space Complexity: O(1) as we only use a few counters and pointers regardless of input size.

Solution

We traverse the linked list two nodes at a time. For every pair, extract the even-indexed node’s value and its subsequent odd-indexed node’s value. Compare these two values and increment the corresponding team's point counter. Finally, after processing all pairs, compare the point counters to decide the winner or determine a tie.

Data Structures and Algorithms:

  • Linked List Traversal with a pointer that skips two nodes at each iteration.
  • Simple arithmetic operations to compare values.
  • Use counters to keep track of team points.

Important Details:

  • Make sure to traverse the list in pairs.
  • The given constraints guarantee that the odd-indexed value is odd and the even-indexed value is even.

Code Solutions

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

def winnerOfLinkedListGame(head: ListNode) -> str:
    odd_points = 0  # Points for the team whose number is in the odd-indexed node
    even_points = 0  # Points for the team whose number is in the even-indexed node
    
    current = head
    # Process pairs of nodes
    while current and current.next:
        even_val = current.val      # Even-indexed node's value
        odd_val = current.next.val  # Odd-indexed node's value
        
        if odd_val > even_val:
            odd_points += 1
        elif even_val > odd_val:
            even_points += 1
        
        # Move to the next pair
        current = current.next.next
    
    # Compare total points to decide the winner
    if odd_points > even_points:
        return "Odd"
    elif even_points > odd_points:
        return "Even"
    else:
        return "Tie"
← Back to All Questions