原文链接: https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list

英文原文

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

 

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Example 3:

Input: head = [1], k = 1
Output: [1]

Example 4:

Input: head = [1,2], k = 1
Output: [2,1]

Example 5:

Input: head = [1,2,3], k = 2
Output: [1,2,3]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

中文题目

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

通过代码

高赞题解

解题思路

声明三个节点cur、first、last全部指向head节点

利用cur从头结点开始遍历链表，
first指针移动k - 1步后定位至该链表正数第k个节点,

设链表的节点个数为nums，当first指针指向第k个节点时，
此时链表还有nums - k个节点没有遍历。

因为链表的头节点到倒数第k个节点之间的节点个数刚好也是nums - k个，
所以当遍历到正数第k个节点后，
last指针开始从head节点移动nums - k步后即指向了倒数第k个节点。

代码

/**
 * 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;
        // 用来定位正数第k个节点
        ListNode first = head;
        // 用来定位倒数第k个节点
        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;
    }
}

统计信息

通过次数	提交次数	AC比率
11796	18278	64.5%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言