Swap Kth nodes from ends

JavaView on GFG

Time: O(n)

Space: O(1)

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?