1721. 交换链表中的节点

题目链接

给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

示例 1：

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

示例 2：

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]

示例 3：

输入：head = [1], k = 1
输出：[1]

示例 4：

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

示例 5：

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

提示：

• 链表中节点的数目是 n
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

解法

1. 双指针

使用双指针可以一次遍历就能得到两个节点的位置。遍历过程需要使用三个指针：

• cur: 遍历链表的指针
• left: 指向左边待交换节点的指针
• right：指向右边待交换节点的指针

1. 一开始 left 和 cur 指针一起遍历链表，直到遍历到第 k 位，此时 left 已经指向了需要交换的第一个节点。
2. 设链表长度为 len，接着如果 cur 指针走到链表末尾需要走 len - k 位，这个值正好是 right 指针的位置，所以此时 right 指针开始和 cur 指针一起右移。
3. 交换 left 和 right 指针指向的节点即可。

下面代码为了交换节点方便指向了待交换节点的前置节点位置。

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        // 指向左边待交换节点的前置节点
        ListNode left = dummyHead;
        // 指向右边待交换节点的前置节点
        ListNode right = dummyHead;
        while (head != null) {
            head = head.next;
            k--;
            if (k > 0) {
                // 左指针移向第 k-1 位
                left = left.next;
                continue;
            }
            if (k < 0) {
                // 右指针开始移向第 len-k-1 位
                right = right.next;
            }
        }
        // 交换两个节点
        if (right.next == left) {
            // 两个节点相邻，且 right 在 left 前面，需要交换下位置
            swap(right, left);
        } else {
            swap(left, right);
        }
        return dummyHead.next;
    }

    /**
     * 交换链表中两个节点的位置
     */
    public void swap(ListNode left, ListNode right) {
        // 两个节点相邻，left节点在right节点前面
        if (left.next == right) {
            ListNode tmp = right.next;
            left.next.next = tmp.next;
            tmp.next = right;
            left.next = tmp;
            return;
        }
        // 两个节点不相邻
        ListNode tmp = left.next.next;
        left.next.next = right.next.next;
        right.next.next = tmp;
        tmp = left.next;
        left.next = right.next;
        right.next = tmp;
    }
}