# Swapping Nodes in a Linked List

### **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* `k<sup>th</sup>` *node from the beginning and the* `k<sup>th</sup>` *node from the end (the list is* ***1-indexed****).*

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

### **Problem Explanation with examples:-**

**Example 1**

![](https://assets.leetcode.com/uploads/2020/09/21/linked1.jpg align="left")

```markdown
Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]
Explanation: 2nd node from the front (head) is 2 and 2nd node from the back is 4. Swap their values and return.
```

**Example 2**

```markdown
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]
Explanation: 5th node from the front (head) is 7 and 5th node from the back is 8. Swap their values and return.
```

**Constraints**

* The number of nodes in the list is `n`.
    
* `1 <= k <= n <= 10<sup>5</sup>`
    
* `0 <= Node.val <= 100`
    

### Intuition:-

* We simply make two iterations for the kth node from the front and the kth node from the back by using two variables to store the nodes.
    
* Then we simply swap the values of the two nodes and return the head.
    

### Solution:-

* Initialize two variables fval and bval to head.
    
* Initialize a variable n to 0 for storing the length of the linked list and a variable curr to head.
    
* Iterate over the linked list and increment n and curr.
    
* Then we iterate over the linked list again for k-1 times and update fval to [fval.next](http://fval.next). This will give us the kth node from the front.
    
* Then we update k to n-k+1 and iterate over the linked list again for k-1 times and update bval to [bval.next](http://bval.next). This will give us the kth node from the back.
    
* Then we simply swap the values of the two nodes and return the head.
    

### Code:-

JAVA Solution

```java
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode tmp = head;
        ListNode p = head;
        ListNode q = head;
        int n=0;
        while(tmp != null){
            n++;
            tmp = tmp.next;
        }
        int a = k;
        while(a > 1){
            p = p.next;
            a--;
        }
        
        int b = n - k + 1;
        while(b > 1){
            q = q.next;
            b--;
        }
        
        int t = p.val;
        p.val = q.val;
        q.val = t;
        
        return head;
    }
}
```

Python Solution

```python
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        fval = head
        bval = head
        n = 0
        curr = head
        while curr:
            curr = curr.next
            n += 1
        
        for i in range(k-1):
            fval = fval.next

        k = n-k+1

        for i in range(k-1):
            bval = bval.next
        
        fval.val, bval.val = bval.val, fval.val
        return head
```

### Complexity Analysis:-

**TIME**:-

The time complexity is **O(n)** where n is the length of the linked list as we make two iterations over the linked list. One for calculating the length and the other for finding the kth node from the front and the back.

**SPACE**:-

The space complexity is **O(1)** as we do not use any extra space.

### References:-

* [**Linked List**](https://www.geeksforgeeks.org/data-structures/linked-list/)
    

### Connect with me:-

* [**Twitter**](https://twitter.com/lakshit_cs)
    
* [**Github**](https://github.com/Lakshit-Chiranjiv)
    
* [**LinkedIn**](https://www.linkedin.com/in/lakshit-chiranjiv-sagar-4b0b15198/)