Question

3062. 链表游戏的获胜者

English Version

题目描述

给定长度为 偶数 ，包含整数的链表的 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)$。

# 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';
}