Winner of the Linked List Game - Practice Coding Problems

Winner of the Linked List Game - Problem

Linked List Easy

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. For example:

Nodes with indices 0 and 1 are a pair
Nodes with indices 2 and 3 are a pair
And so on...

For every pair, we compare the values:

If the odd-indexed node value is higher → "Odd" team gets a point
If the even-indexed node value is higher → "Even" team gets a point

Return the name of the team with the higher points. If the points are equal, return "Tie".

Input & Output

Example 1 — Basic Case

$ Input: head = [2,7,4,9]

› Output: Odd

💡 Note: Pair 1: (2,7) → 7 > 2, Odd gets 1 point. Pair 2: (4,9) → 9 > 4, Odd gets 1 point. Final score: Even=0, Odd=2, so Odd wins.

Example 2 — Even Team Wins

$ Input: head = [8,3,6,1]

› Output: Even

💡 Note: Pair 1: (8,3) → 8 > 3, Even gets 1 point. Pair 2: (6,1) → 6 > 1, Even gets 1 point. Final score: Even=2, Odd=0, so Even wins.

Example 3 — Tie Game

$ Input: head = [10,5,2,7]

› Output: Tie

💡 Note: Pair 1: (10,5) → 10 > 5, Even gets 1 point. Pair 2: (2,7) → 7 > 2, Odd gets 1 point. Final score: Even=1, Odd=1, so it's a Tie.

Constraints

The linked list has even length
2 ≤ length ≤ 100
Each odd-indexed node contains an odd integer
Each even-indexed node contains an even integer
1 ≤ Node.val ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list with alternating even/odd values at even/odd indices

Pair Formation

Group adjacent nodes into pairs and compare values

Score & Winner

Count wins for each team and determine the winner

Key Takeaway

🎯 Key Insight: Process the linked list in pairs, comparing adjacent nodes to track team scores efficiently in a single pass

Asked in

M Microsoft 15 a Amazon 12 G Google 8

The key insight is to traverse the linked list in pairs, comparing adjacent even-odd nodes and tracking team scores. The optimal approach uses a single pass with O(n) time and O(1) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Traversal	O(n)	O(1)	Traverse the linked list once, comparing each pair and tracking scores
Score Difference Tracking	O(n)	O(1)	Track only the score difference instead of separate counters

Single Pass Traversal — Algorithm Steps

Step 1: Initialize counters for Even and Odd teams
Step 2: Traverse list in pairs, comparing adjacent nodes
Step 3: Increment appropriate team counter based on comparison
Step 4: Return winner based on final scores

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set counters for Even and Odd teams to 0

Compare Pairs

Compare each even-indexed node with its odd-indexed neighbor

Determine Winner

Return team with higher score or 'Tie' if equal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

char* solution(struct ListNode* head) {
    int evenScore = 0;
    int oddScore = 0;
    
    struct ListNode* current = head;
    while (current && current->next) {
        int evenVal = current->val;      // even index
        int oddVal = current->next->val;  // odd index
        
        if (evenVal > oddVal) {
            evenScore++;
        } else {
            oddScore++;
        }
        
        current = current->next->next;  // move to next pair
    }
    
    char* result = malloc(5);
    if (evenScore > oddScore) {
        strcpy(result, "Even");
    } else if (oddScore > evenScore) {
        strcpy(result, "Odd");
    } else {
        strcpy(result, "Tie");
    }
    return result;
}

struct ListNode* buildLinkedList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing for [a,b,c,d] format
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    struct ListNode* head = buildLinkedList(arr, size);
    char* result = solution(head);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal through all n nodes in the linked list

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for counters and pointers

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Traversal — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler