3062. 链表游戏的获胜者 🔒

题目描述

给定长度为偶数，包含整数的链表的 head 节点。

每个 奇数编号 的节点包含一个奇数，并且每个 偶数编号 的节点包含一个偶数。

我们把每个偶数编号的节点和它的下一个节点叫做一个对，例如编号为 0 和 1 的节点是一对，编号为 2 和 3 的节点是一对，以此类推。

对于每个对，我们比较对中节点的值：

如果奇数节点更大，"Odd" 队得一分。
如果偶数节点更大，"Even" 队得一分。

返回分数更高的队名，如果分数相同，返回 "Tie"。

示例 1：

输入：head = [2,1]
输出："Even"
解释：链表中只有一个对 (2,1)。因为 2 > 1，偶数队得分。
因此，答案是 "Even"。

示例 2：

输入：head = [2,5,4,7,20,5] 
输出："Odd" 
解释：此链表中有 3 对。让我们分别对每一对进行分析： 
(2,5) -> 因为 2 < 5，奇数队得分。
(4,7) -> 因为 4 < 7，奇数队得分。 
(20,5) -> 因为 20 > 5，偶数队得分。 
奇数队得 2 分，偶数队得 1 分，奇数队得分更高。 
因此，答案是 "Odd"。

示例 3：

输入：head = [4,5,2,1]
输出："Tie"
解释：此链表中有 2 对。让我们分别对每一对进行分析：
(4,5) -> 因为 4 < 5，奇数队得分。
(2,1) -> 因为 2 > 1，偶数队得分。
每队得 1 分。
因此，答案是 "Tie"。

提示：

链表中节点的数字在范围 [2, 100] 内。
链表中的节点数为偶数。
1 <= Node.val <= 100
每个奇数编号节点的值都是奇数。
每个偶数编号节点的值都是偶数。

解法

方法一：模拟

遍历链表，每次取出两个节点，比较它们的值，然后根据比较结果更新奇数和偶数的得分。最后比较奇数和偶数的得分，返回结果。

时间复杂度 $O(n)$，其中 $n$ 是链表的长度。空间复杂度 $O(1)$。

Python3JavaC++GoTypeScript

# Definition for singly-linked 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 singly-linked 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 singly-linked 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 singly-linked 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 singly-linked 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';
}

3062. 链表游戏的获胜者 🔒

题目描述

解法

方法一：模拟

评论