标签： 链表

目标

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

示例 1：

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。 

示例 2：

输入：head = [1,2,3,4]
输出：[1,2,4]
解释：
上图表示给出的链表。
对于 n = 4 ，值为 3 的节点 2 是中间节点，用红色标注。

示例 3：

输入：head = [2,1]
输出：[2]
解释：
上图表示给出的链表。
对于 n = 2 ，值为 1 的节点 1 是中间节点，用红色标注。
值为 2 的节点 0 是移除节点 1 后剩下的唯一一个节点。

说明：

• 链表中节点的数目在范围 [1, 10^5] 内
• 1 <= Node.val <= 10^5

思路

删除链表的中间节点。

使用快慢指针，开始时都指向头节点，快指针每次走两步，慢指针走一步。当快指针指向最后一个节点或者 null 时，慢指针指向中间节点。因此需要在慢指针更新前将节点删除掉。

代码

/**
 * @date 2026-06-15 8:59
 */
public class DeleteMiddle2095 {

    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (true) {
            fast = fast.next.next;
            if (fast == null || fast.next == null) {
                slow.next = slow.next.next;
                break;
            }
            slow = slow.next;
        }
        return head;
    }

}

性能

目标

在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。

• 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

示例 1：

输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。

示例 2：

输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。

示例 3：

输入：head = [1,100000]
输出：100001
解释：
链表中只有一对孪生节点，孪生和为 1 + 100000 = 100001 。

说明：

• 链表的节点数目是 [2, 10^5] 中的 偶数 。
• 1 <= Node.val <= 10^5

思路

有一个节点个数为偶数的链表，节点 A 的孪生节点 B 需满足 A 到 head 的距离等于 B 到 tail 的距离，通俗来说就是关于中轴线对称。每对孪生节点的和称为孪生和，求链表最大的孪生和。

快慢指针找到中间节点，然后反转链表后半部分，空间复杂度为 O(1)。

代码

/**
 * @date 2026-06-15 14:06
 */
public class PairSum2130 {

    public int pairSum(ListNode head) {
        int res = 0;
        ListNode slow = head;
        ListNode fast = head;
        int cnt = 0;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            cnt++;
        }
        ListNode prev = slow;
        slow = slow.next;
        prev.next = null;
        while (slow != null) {
            ListNode tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }
        for (int i = 0; i < cnt; i++) {
            res = Math.max(res, prev.val + head.val);
            prev = prev.next;
            head = head.next;
        }
        return res;
    }

}

性能

目标

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

说明：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

思路

将链表的每个节点右移 k 个位置，即将链表最后 k % list.size() 个元素放到列表头。

可以使用快慢指针，slow 指向最后 k 个节点的前面一个节点，slow 指针移到到 fast 指针需要移动 k + 1 次，即后面 k 个节点和 null。先让 fast 移动 k + 1 次，再让 slow 与 fast 同时移动。

代码

/**
 * @date 2024-11-24 16:15
 */
public class RotateRight61 {

    public ListNode rotateRight_v1(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int length = 1;
        ListNode last = head;
        while (last.next != null) {
            last = last.next;
            length++;
        }
        k = k % length + 1;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            k--;
            if (k < 0) {
                slow = slow.next;
            }
        }
        last.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }

}

性能

目标

给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。

示例 1：

输入： nums = [1,2,3], head = [1,2,3,4,5]
输出： [4,5]
解释：
移除数值为 1, 2 和 3 的节点。

示例 2：

输入： nums = [1], head = [1,2,1,2,1,2]
输出： [2,2,2]
解释：
移除数值为 1 的节点。

示例 3：

输入： nums = [5], head = [1,2,3,4]
输出： [1,2,3,4]
解释：
链表中不存在值为 5 的节点。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• nums 中的所有元素都是唯一的。
• 链表中的节点数在 [1, 10^5] 的范围内。
• 1 <= Node.val <= 10^5
• 输入保证链表中至少有一个值没有在 nums 中出现过。

思路

依题意模拟即可，删除链表中的指定节点。

代码

/**
 * @date 2025-11-03 13:55
 */
public class ModifiedList3217 {

    public ListNode modifiedList_v1(int[] nums, ListNode head) {
        Set<Integer> set = new HashSet<>(nums.length, 1);
        for (int num : nums) {
            set.add(num);
        }
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        while (head != null) {
            if (set.contains(head.val)) {
                prev.next = head.next;
            } else {
                prev = head;
            }
            head = head.next;
        }
        return dummy.next;
    }

}

/**
 * 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; }
 * }
 */

性能