Leetcode 1721. Swapping Nodes in a Linked List [Solution]
Tags: algorithms, programming, cpp, tutorial
Published: 2021-03-14 13:40:08

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](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>

**Question:** [https://leetcode.com/problems/swapping-nodes-in-a-linked-list/](https://leetcode.com/problems/swapping-nodes-in-a-linked-list/)



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:**

![Linked List Image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gqiic61f3e0jigcrtmfu.jpg)

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

**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 <a name="explanation"></a>

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 <a name="solution"></a>

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 <a name="implementation"></a>

**C++ Code:**
```cpp
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:**

{% replit @shivams136/Leetcode-1721-Swapping-Nodes-in-a-Linked-List %}