Reverse every alternate k nodes of a Linked List

Algorithm/Insights

It is recommended to go through
Reverse a Linked List - Iterative
Reverse a Linked List - Recursive

1. Traverse k nodes forward and set temp to the k+1th node
2. Reverse k nodes traversed in step 1. Here is a post on how to reverse a linked list: Reverse a Linked List
3. Set next of the last node in this k length list to temp.
4. Traverse next k nodes which are to be skipped.
5. Recursively call steps 1-3 for reversing next k nodes.

Code Snippet

			
package com.ideserve.questions.saurabh;

/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* Reverse every alternate k nodes of a Linked List.
*
* @author Saurabh
*/
public class LinkedList {

    private ListNode head;

    public void add(int data) {
        if (head == null) {
            head = new ListNode(data);
            return;
        }

        ListNode n = new ListNode(data);
        ListNode tmp = head;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = n;
    }

    public void printList() {
        if (head == null) {
            System.out.println("List is empty!");
            return;
        }
        ListNode tmp = head;
        while (tmp != null) {
            System.out.print(tmp.data + " -> ");
            tmp = tmp.next;
        }
        System.out.println("null");
    }

    public void reverseKAlternateNodes(int k) {
        if (head == null || head.next == null || k < 2) {
            return;
        }
        head = reverseKAlternateNodes(head, k);
    }

    // Reverse alternate k nodes
    public ListNode reverseKAlternateNodes(ListNode head, int k) {
        if (head == null || head.next == null || k < 2) {
            return head;
        }

        // get k+1th node
        ListNode temp = head;
        int i = 0;
        while (i < k && temp != null) {
            temp = temp.next;
            i++;
        }

        // reverse nodes upto k nodes traversed previously
        head = reverseKNodes(head, k);
        ListNode next = head;
        while (next.next != null) {
            next = next.next;
        }
        next.next = temp;

        // Traverse next k nodes
        i = 0;
        ListNode prev = null;
        while (i < k && temp != null) {
            prev = temp;
            temp = temp.next;
            i++;
        }

        if (temp != null) {
            prev.next = this.reverseKAlternateNodes(temp, k);
        }

        return head;
    }

    // Reverse k nodes starting from start node
    private ListNode reverseKNodes(ListNode start, int k) {

        if (start == null || k < 2) {
            return null;
        }

        ListNode prev = null;
        ListNode curr = start;
        ListNode next = null;

        int i = 1;
        while (curr.next != null && i < k) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            i++;
        }
        next = curr.next;
        curr.next = prev;
        return curr;
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        for (int i = 1; i <= 10; i++) {
            list.add(i);
        }
        list.printList();
        list.reverseKAlternateNodes(4);
        list.printList();
    }
}

class ListNode {

    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)