Swap Kth nodes from ends

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Swap values of kth node from beginning and kth node from end in linked list.

Intuition

Swap values of kth node from beginning and kth node from end in linked list.

Algorithm

1Find kth from start (advance k steps). Find kth from end (two pointers). Swap their values.

Common Pitfalls

• Same as LC 1721. Two-pointer for kth from end. Just swap values, not node pointers.

Swap Kth nodes from ends.java

Java

// Approach: Find k-th from start and k-th from end using two-pointer. Swap only the data values.
// Time: O(n) Space: O(1)
class Node {
    int data;
    Node next;

    Node(int x) {
        data = x;
        next = null;
    }
}

class Solution {
    public Node swapKth(Node head, int k) {
        Node f_num = head;
        Node l_num = head;

        int c = countNode(head);
        int x = c - k + 1;

        if (k > c)
            return head;

        while (k > 0) {
            k--;
            if (k > 0)
                f_num = f_num.next;
        }

        while (x > 0) {
            x--;
            if (x > 0)
                l_num = l_num.next;
        }

        int temp = f_num.data;
        f_num.data = l_num.data;
        l_num.data = temp;

        return head;
    }

    private int countNode(Node head) {
        int c = 0;
        while (head != null) {
            c++;
            head = head.next;
        }

        return c;
    }
}

Was this solution helpful?