Question

1721. Swapping Nodes in a Linked List

中文文档

Description

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]

 

Constraints:

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

Solutions

Solution 1: Two Pointers

We can first use a fast pointer fast to find the $k$th node of the linked list, and use a pointer p to point to it. Then, we use a slow pointer slow to start from the head node of the linked list, and move both pointers forward at the same time. When the fast pointer reaches the last node of the linked list, the slow pointer slow points to the $k$th node from the end of the linked list, and we use a pointer q to point to it. At this point, we only need to swap the values of p and q.

The time complexity is $O(n)$, where $n$ is the length of the linked list. The space complexity is $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;
  }
}