# 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)$.

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

• /**
* 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) {
while (--k) {
fast = fast->next;
}
ListNode* p = fast;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
ListNode* q = slow;
swap(p->val, q->val);
}
};

• # 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]:
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


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

• /**
* 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 {
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];
}


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