跳转至

1721.交换链表中的节点

题目描述

原题

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

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

示例 1：

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

示例 2：

1
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：

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

示例 4：

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

示例 5：

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

提示：

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

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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) {
        //fast先走k步获取第k个
        //创建slow两个一起走 fast为null时slow就等于倒数第k个
        //然后就行交换
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        ListNode fast = dummyNode;
        for(int i = 0;i < k && fast!=null ;i++){
            fast = fast.next;
        }
        ListNode firstK = fast;
        ListNode slow = dummyNode;
        while(fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        ListNode lastK = slow;
        //判断两个值是否相等 不相等就就进行交换
        if(firstK.val != lastK.val){
            int temp = firstK.val;
            firstK.val = lastK.val;
            lastK.val = temp;
        }
        return dummyNode.next;
    }
}