Swapping k-th Nodes in a Linked List Using Java

Introduction:

In this tutorial, we will explore how to swap the k-th node from the beginning with the k-th node from the end in a singly linked list using Java. This operation is a common task in data structures and algorithms, especially when manipulating linked lists. We will walk through the concept, implementation, and provide a complete Java code example.

Concept:

Swapping the k-th node from the beginning with the k-th node from the end in a linked list involves re-arranging the nodes’ positions while maintaining the list’s structure. This can be useful in various scenarios, such as reversing segments of the list or reordering data.

Here’s a step-by-step guide to achieve this:

1. Identify the Nodes to Swap:
   • k-th node from the beginning (first).
   • k-th node from the end (second).
2. Swap Nodes:
   • Exchange the positions of the identified nodes without altering the remaining list.
3. Handle Edge Cases:
   • If k is greater than the length of the list.
   • If k is zero or negative.
   • If the nodes to be swapped are the same.

Java Code Implementation:

Below is the complete Java code to perform the k-th node swap in a linked list:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedListSwapKth {

    // Function to swap kth node from beginning with kth node from end
    public static ListNode swapKthNode(ListNode head, int k) {
        if (head == null || k <= 0) {
            return head; // Edge case: Empty list or invalid k
        }

        // Step 1: Find the length of the list
        int length = 0;
        ListNode current = head;
        while (current != null) {
            length++;
            current = current.next;
        }

        if (k > length) {
            return head; // Edge case: k is greater than the length of the list
        }

        // Step 2: Find the k-th node from the beginning
        ListNode firstPrev = null;
        ListNode first = head;
        for (int i = 1; i < k; i++) {
            firstPrev = first;
            first = first.next;
        }

        // Step 3: Find the k-th node from the end
        ListNode secondPrev = null;
        ListNode second = head;
        for (int i = 1; i < length - k + 1; i++) {
            secondPrev = second;
            second = second.next;
        }

        // If both nodes are the same, no need to swap
        if (first == second) {
            return head;
        }

        // Step 4: Swap the nodes
        if (firstPrev != null) {
            firstPrev.next = second;
        } else {
            head = second; // if k is 1, the head will be swapped
        }

        if (secondPrev != null) {
            secondPrev.next = first;
        } else {
            head = first; // if k is the length, the head will be swapped
        }

        // Swap next pointers
        ListNode temp = first.next;
        first.next = second.next;
        second.next = temp;

        return head;
    }

    // Utility function to print the list
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Create a sample list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.println("Original List:");
        printList(head);

        int k = 2;
        head = swapKthNode(head, k);

        System.out.println("List after swapping " + k + "-th node from beginning and end:");
        printList(head);
    }
}

Explanation of the Code:

1. Node Definition: The ListNode class defines a node in the singly linked list with a value and a pointer to the next node.
2. Main Function (swapKthNode):
   • Finding Length: Traverse the list to find its length.
   • Locating Nodes: Use loops to find the k-th node from the beginning (first) and the k-th node from the end (second).
   • Swapping Nodes: Adjust the pointers of the previous and current nodes to swap their positions.
3. Utility Function (printList): A helper function to print the list, useful for verifying the result.

Example:

Consider the list [1,2,3,4,5][1, 2, 3, 4, 5][1,2,3,4,5] with k=2k = 2k=2. The 2nd node from the beginning is 2, and the 2nd node from the end is 4. After swapping these nodes, the list becomes [1,4,3,2,5][1, 4, 3, 2, 5][1,4,3,2,5].

Conclusion:

Swapping nodes in a linked list can be a useful operation for various algorithms. The provided Java code efficiently swaps the k-th node from the beginning with the k-th node from the end, handling edge cases gracefully. You can integrate this approach into your projects to manipulate linked lists as needed.