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

#algorithms #programming #cpp #tutorial

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
Explanation
Solution
Implementation

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:

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.

Point a pointer x to the head.
Move the pointer forward in the linked list until we reached k-th node.

Step 2: Point to k-th node from the end.

Point 2 pointers y and t to the head.
Move pointer t till k-th node.
Now move both the pointers y & t until t has reached the last node.
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;
    }
};