Swapping Nodes in a Linked List Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Bloomberg Facebook MicrosoftViews 21

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 kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example:

Swapping Nodes in a Linked List Leetcode SolutionPin

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

Code

C++ Code

class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        
        ListNode* tmp = head;
        int ct = k;
        ListNode* res1 = head;
        ListNode* res2 = head;
        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);
        return head;
    }
};

Java Code

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode tmp = head;
        int ct = k;
        ListNode res1 = head;
        ListNode res2 = head;
        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;
        return head;
    }
}

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 »