Question

1721. 交换链表中的节点

English Version

题目描述

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

解法

方法一：快慢指针

我们可以先用快指针 $fast$ 找到链表的第 $k$ 个节点，用指针 $p$ 指向它。然后我们再用慢指针 $slow$ 从链表的头节点出发，快慢指针同时向后移动，当快指针到达链表的最后一个节点时，慢指针 $slow$ 恰好指向倒数第 $k$ 个节点，用指针 $q$ 指向它。此时，我们只需要交换 $p$ 和 $q$ 的值即可。

时间复杂度 $O(n)$，其中 $n$ 是链表的长度。空间复杂度 $O(1)$。

# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#     self.val = val
#     self.next = next
class Solution:
  def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    fast = slow = head
    for _ in range(k - 1):
      fast = fast.next
    p = fast
    while fast.next:
      fast, slow = fast.next, slow.next
    q = slow
    p.val, q.val = q.val, p.val
    return head

/**
 * 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 fast = head;
    while (--k > 0) {
      fast = fast.next;
    }
    ListNode p = fast;
    ListNode slow = head;
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    ListNode q = slow;
    int t = p.val;
    p.val = q.val;
    q.val = t;
    return head;
  }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *   int val;
 *   ListNode *next;
 *   ListNode() : val(0), next(nullptr) {}
 *   ListNode(int x) : val(x), next(nullptr) {}
 *   ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
  ListNode* swapNodes(ListNode* head, int k) {
    ListNode* fast = head;
    while (--k) {
      fast = fast->next;
    }
    ListNode* slow = head;
    ListNode* p = fast;
    while (fast->next) {
      fast = fast->next;
      slow = slow->next;
    }
    ListNode* q = slow;
    swap(p->val, q->val);
    return head;
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func swapNodes(head *ListNode, k int) *ListNode {
  fast := head
  for ; k > 1; k-- {
    fast = fast.Next
  }
  p := fast
  slow := head
  for fast.Next != nil {
    fast, slow = fast.Next, slow.Next
  }
  q := slow
  p.Val, q.Val = q.Val, p.Val
  return head
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   val: number
 *   next: ListNode | null
 *   constructor(val?: number, next?: ListNode | null) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 *   }
 * }
 */

function swapNodes(head: ListNode | null, k: number): ListNode | null {
  let [fast, slow] = [head, head];
  while (--k) {
    fast = fast.next;
  }
  const p = fast;
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  const q = slow;
  [p.val, q.val] = [q.val, p.val];
  return head;
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *   public int val;
 *   public ListNode next;
 *   public ListNode(int val=0, ListNode next=null) {
 *     this.val = val;
 *     this.next = next;
 *   }
 * }
 */
public class Solution {
  public ListNode SwapNodes(ListNode head, int k) {
    ListNode fast = head;
    while (--k > 0) {
      fast = fast.next;
    }
    ListNode p = fast;
    ListNode slow = head;
    while (fast.next != null) {
      fast = fast.next;
      slow = slow.next;
    }
    ListNode q = slow;
    int t = p.val;
    p.val = q.val;
    q.val = t;
    return head;
  }
}