leetcode1721. 交换链表中的节点

末蓝、 2022-11-06 01:59 5阅读 0赞

给你链表的头节点 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

思路：两个指针找到以后交换值即可。

‘

/**
     * 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 ListNode swapNodes(ListNode head, int k) {
            ListNode cur = head;
            ListNode first = head;
            ListNode last = head;
            int count = 1;
            while (cur.next != null) {
                // 找到正数第k个节点
                if (count < k) {
                    first = first.next;
                // 找到倒数第k个节点
                } else {
                    last = last.next;
                }
                count++;
                cur = cur.next;
            }
            // 交换正数第k个节点和倒数第k个节点的值
            count = first.val;
            first.val = last.val;
            last.val = count;
            return head;
        }
    }