双周赛第69场:LeetCode:5961.链表最大孪生和

浏览次数 : 次 2022-01-09

博文字数统计 : 1.1k字 | 阅读所需时长 : 4分

× 文章目录

1. 双周赛第69场：LeetCode：5961.链表最大孪生和

双周赛第69场：LeetCode：5961.链表最大孪生和
- 时间：2022-01-08
- 力扣难度：Medium
- 个人难度：Medium-
- 数据结构：链表
- 算法：快慢指针、双指针

双周赛第69场：LeetCode：5961.链表最大孪生和

1. 题目描述

题目：原题链接
- 在一个大小为 n 且 n 为偶数的链表中，对于 $0 <= i <= (n / 2) - 1$ 的 i ，第 i 个节点的孪生节点为第 $n-1-i$ 个节点
- 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
- 孪生和：定义为一个节点和它孪生节点两者值之和。
- 给你一个长度为偶数的链表的头节点 head ，请你返回链表的最大孪生和。
输入输出规范
- 输入：链表头节点head
- 输出：最大的孪生和
输入输出示例
- 输入：head = [5,4,2,1]
- 输出：6

2. 方法一：暴力模拟

思路
- 根据题意可知，孪生和实际上就是根据链表中点两侧对称的节点的值的和，且输入的链表长度一定为偶数，即可以通过确定的下标来计算每一个孪生和
- 但是链表无法同时获取不同指定下标的元素，所以可以将其值储存到数组、列表等结构中
- 首先，循环遍历一次链表，将其中的值取出来存放到一个List中
- 然后，遍历该List，只需要遍历到该List的一半即可，循环中动态维护最大的孪生和
复杂度分析：n是字符串的长度
- 时间复杂度：$O(n)$，遍历链表$O(n)$，遍历半个List$O(n/2)$
- 空间复杂度：$O(n)$

题解：直接模拟

public int pairSum(ListNode head) {
       if(head == null) return 0;
       List<Integer> valList = new ArrayList<>();
       valList.add(head.val);
       while(head.next != null) {
           head = head.next;
           valList.add(head.val);
       }
       int n = valList.size();
       int maxTwinSum = 0;
       for(int i = 0; i < n/2; i++) {
           maxTwinSum = Math.max(maxTwinSum, valList.get(i) + valList.get(n - i - 1));
       }
       return maxTwinSum;
   }

3. 方法二：双指针 & 快慢指针

思路：寻找链表中点、后半链表反转、求孪生和
- 方法一的暴力模拟使用了额外的List储存链表的节点值，浪费空间
- 为了避免空间浪费，可以仅在链表上完成求解孪生和操作，由于孪生元素分别为第 i 个元素和第 $n-1-i$ 个元素，链表无法直接根据下标获取元素
- 所以我们对链表进行一些修改，具体而言，分为以下三步
  - 需要通过快慢指针获取链表中点
  - 在中点位置将链表断开，由于是单向链表，无法从后向前获取元素，所以需要反转后半部分链表
  - 通过双指针的方式，同时遍历前半、后半链表，计算孪生和并找到其最大值
复杂度分析：n是字符串的长度
- 时间复杂度：$O(n)$，寻找链表中点$O(n/2)$，后半个链表反转$O(n/2)$，求孪生和$O(n/2)$
- 空间复杂度：$O(1)$，无需额外空间

题解：快慢指针+双指针

public int pairSum(ListNode head) {
    if (head == null) return 0;
    ListNode fast = head;
    ListNode slow = head;
    // 1. 寻找链表中点
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    // 2. 反转后半链表
    ListNode cur = slow;
    ListNode prev = null;
    while (cur != null) {
        ListNode temp = cur.next;
        cur.next = prev;
        prev = cur;
        cur = temp;
    }

    // 3. 计算孪生和
    int maxTwinSum = 0;
    while(head != null && prev != null) {
        maxTwinSum = Math.max(maxTwinSum, head.val + prev.val);
        head = head.next;
        prev = prev.next;
    }
    return maxTwinSum;
}

思考：时间复杂度
- 虽然根据分析可得，两种方式的时间复杂度都是$O(n)$，但是实际上在LeetCode平台提交测试的结果却有较大差异
- 以Java为例，使用了List的暴力法约为10ms，而使用快慢指针的第二种方法只需要4ms，注意参考的日期是2022-01-09，不同时间可能后台的测试用例不同
- 复杂度是同一级别，但是结果缺相差较大，个人分析可能是对于List方式而言，List在逐个添加链表元素时，如果链表长度较大(本题为$0<n<10^5$)，就需要对List不断进行扩容，从而耗费更多的时间
- 如果大家觉得有其他的因素导致该现象，欢迎评论区分享~ ~ ~

本文作者： Chthollists
发布时间： 2022-01-09 19:35:21
最后更新： 2022-01-27 20:44:38
本文标题： 双周赛第69场:LeetCode:5961.链表最大孪生和
本文链接： https://chthollists.github.io/post/34fd8a39.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！