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/

Problem Explanation with examples:-

Example 1

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

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. 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. 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

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

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

Connect with me:-

• Twitter

• Github

• LinkedIn