DEV Community

Cover image for Leetcode 1721. Swapping Nodes in a Linked List [Solution]
Shivam Sharma
Shivam Sharma

Posted on • Updated on

Leetcode 1721. Swapping Nodes in a Linked List [Solution]

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

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

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

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

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

C++ Code:

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;
    }
};
Enter fullscreen mode Exit fullscreen mode
  • Time Complexity: O(N), where N is the length of linked list.
  • Space Complexity: O(1)

Runnable C++ code:

Top comments (1)

Collapse
 
johnhere12 profile image
johnhere12

I used this code and modify it according to my requirement..