## DEV Community is a community of 638,230 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

loading... # Leetcode 1721. Swapping Nodes in a Linked List [Solution] Shivam Sharma Updated on ・3 min read

If we get the idea correctly then this question is just a combination of two general questions, first one is "Find `k-th` node from the end in a linked list" and "Swap two numbers". As instead of swapping the nodes, swapping the data of the nodes is sufficient. If you are going to swap actual nodes then this is going to be a little bit more tricky. But you can try that as well to test yourself. We are going to solve this question using the above logic.

Difficulty: Medium
Jump To:

## Problem Statement

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 = , k = 1
Output: 

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`

## Explanation

So the question wants two simple things from us, first one is to find `k-th` node from the beginning and `k-th` node from the end in a linked list. The second thing to be done is to swap both the nodes. As it's not asked to swap the actual node with its address so we can simply just swap the values of the nodes instead of swapping the nodes.

## Solution

The problem needs to be solved in the below steps:

Step 1: Point to `k-th` node from the beginning.

1. Point a pointer `x` to the head.
2. Move the pointer forward in the linked list until we reached `k-th` node.

Step 2: Point to `k-th` node from the end.

1. Point 2 pointers `y` and `t` to the head.
2. Move pointer `t` till `k-th` node.
3. Now move both the pointers `y` & `t` until `t` has reached the last node.
4. So when `t` has reached the last node, `y` must have been reached `k-th` node from the end.

Step-3: Swap values of both the nodes.

As we can guess that `Point 2` of `Step-2` can be done in the same loop of `Point 1` of `Step-1`. This will save a bit of computation for us.

## Implementation

C++ Code:

``````class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
ListNode *x=head, *y=head, *t=head;

// Until we reach k-th node from beginning
while(k>1){
x = x->next;
t = t->next;
k--;
}

// Until pointer t reach last need
while(t->next){
y=y->next;
t=t->next;
}

// Swap values at both the nodes
int temp = x->val;
x->val = y->val;
y->val = temp;

return head;
}
};
``````
• Time Complexity: `O(N)`, where `N` is the length of `linked list`.
• Space Complexity: `O(1)`

Runnable C++ code: