# Swapping Nodes in a Linked List Leetcode Solution

Difficulty Level Medium

## Problem Statement

Swapping Nodes in a Linked List Leetcode Solution – 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).

## Example:

Input:

``` head = [1,2,3,4,5], k = 2
```

Output:

` [1,4,3,2,5]`

## Explanation

Here, the second node from the beginning is 2 and the second node from the end is 4 (marked with blue color), after the swap the output becomes [1,4,3,2,5].

## Approach

### Idea

Here, the simple idea is to take 2 pointers and move them such that one of them points to the Kth node from the start and the other points to the Kth node from the end and then we can just basically swap the data in both of them.

Now how to move the two pointers to their respective positions.

1. For the Kth node from start – We Just move the head pointer (k-1) times ahead so it will point to the Kth node from the start.
2. For the Kth node from the end – We have to do some work here but it’s easy, we first take a temporary pointer and move it by k places ahead and now we take the pointer in which we want to store the result. Now we move the temporary pointer and the result pointer simultaneously until the temporary pointer becomes NULL, So the result pointer will point to the Kth node from the last.

## Code

### C++ Code

```class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {

int ct = k;
while(ct--){
res1 = tmp;
tmp = tmp->next;
}
// moving temporary pointer k times and the Kth node from the beginning pointer is moved (k-1) times.
while(tmp!=NULL){
tmp = tmp->next;
res2 = res2->next;
}
// moving the temporary and res2 pointer simultaneously.
swap(res1->val,res2->val);
}
};```

### Java Code

```class Solution {
public ListNode swapNodes(ListNode head, int k) {
int ct = k;
while(ct>0){
res1 = tmp;
tmp = tmp.next;
ct--;
}
// moving temporary pointer k times and the Kth node from the beginning pointer is moved (k-1) times.
while(tmp!=null){
tmp = tmp.next;
res2 = res2.next;
}
// moving the temporary and res2 pointer simultaneously.

int temp = res1.val;
res1.val = res2.val;
res2.val = temp;
}
}```

## Complexity Analysis for Swapping Nodes in a Linked List Leetcode Solution

### Time Complexity

As we are moving k times in the first loop and (n-k) times in the second loop the overall time complexity is O(n).

### Space Complexity

As we are not using any extra space so space complexity is O(1). We use Two Pointers to make it to `O(1)`.

Translate »