Solution: Swapping Nodes in a Linked List
Tags: algorithms, javascript, java, python
Published: 2021-03-14 09:49:07

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/swapping-nodes-in-a-linked-list/discuss/1108935).*

---

#### [Leetcode Problem #1721 (*Medium*): Swapping Nodes in a Linked List](https://leetcode.com/problems/swapping-nodes-in-a-linked-list/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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 `k`th node from the beginning and the `k`th node from the end (the list is __1-indexed__).

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:|head = [1,2,3,4,5], k = 2
Output:|[1,4,3,2,5]
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/09/21/linked1.jpg)
>
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 <= 10^5`
 - `0 <= Node.val <= 100`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

It's important to notice that the instructions don't specify that we have to actually swap the *nodes*, just the *values*. So the only thing remaining is to just find both nodes.

Since we don't know how long the linked list is, we'll have to iterate to the end of it before we can possibly find the second node to swap out. But to make things easier, we don't have to find and store the length and then calculate the difference, we can just take advantage of the fact that the distance from the **k**th node to the end is the same as the distance from the beginning to the **k**th node from the end.

![Visual 1](https://i.imgur.com/oQ76PFv.png)

We can move the first list (**A**) forward to the **k**th node, making sure to store it in a variable (**nodeK**), then start our staggered list (**B**) and iterate both until **A** ends, at which point we should be at the **k**th node from the end.

Then we just swap the values and **return head**.

---

#### ***Implementation:***

The code for all four languages is almost exactly the same.

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var swapNodes = function(head, k) {
    let A = head, B = head, K, temp
    for (let i = 1; i < k; i++) A = A.next
    K = A, A = A.next
    while (A) A = A.next, B = B.next
    temp = K.val, K.val = B.val, B.val = temp
    return head
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def swapNodes(self, head: ListNode, k: int) -> ListNode:
        A, B = head, head
        for i in range(1, k): A = A.next
        nodeK, A = A, A.next
        while A: A, B = A.next, B.next
        nodeK.val, B.val = B.val, nodeK.val
        return head
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode A = head, B = head, nodeK;
        for (int i = 1; i < k; i++) A = A.next;
        nodeK = A;
        A = A.next;
        while (A != null) {
            A = A.next;
            B = B.next;
        }
        int temp = nodeK.val;
        nodeK.val = B.val;
        B.val = temp;
        return head;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        ListNode *A = head, *B = head, *nodeK;
        for (int i = 1; i < k; i++) A = A->next;
        nodeK = A, A = A->next;
        while (A) A = A->next, B = B->next;
        int temp = nodeK->val;
        nodeK->val = B->val, B->val = temp;
        return head;
    }
};
```