How to reverse a singly-linked list in blocks of some given size in O(n) time in place?

Question

I recently encounter an algorithm problem:

Reverse a singly-linked list in blocks of k in place. An iterative approach is preferred. The first block of the resulting list should be maximal with regards to k. If the list contains n elements, the last block will either be full or contain n mod k elements.

For example:
k = 2, list = [1,2,3,4,5,6,7,8,9], the reversed list is [8,9,6,7,4,5,2,3,1]
k = 3, list = [1,2,3,4,5,6,7,8,9], the reversed list is [7,8,9,4,5,6,1,2,3]

My code is shown as below.

Is there an O(n) algorithm that doesn't use a stack or extra space?

public static ListNode reverse(ListNode list, int k) {
    Stack<ListNode> stack = new Stack<ListNode>();
    int listLen = getLen(list);
    int firstBlockSize = listLen % k;
    ListNode start = list;
    if (firstBlockSize != 0) {
        start = getBlock(stack, start, firstBlockSize);
    }
    int numBlock = (listLen) / k;
    for (int i = 0; i < numBlock; i++) {
        start = getBlock(stack, start, k);
    }
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (!stack.empty()) {
        cur.next = stack.peek();
        cur = stack.pop();
        while (cur.next != null) {
            cur = cur.next;
        }
    }
    return dummy.next;
}

public static ListNode getBlock(Stack<ListNode> stack, ListNode start, int blockSize) {
    ListNode end = start;
    while (blockSize > 1) {
        end = end.next;
        blockSize--;
    }
    ListNode temp = end.next;
    end.next = null;
    stack.push(start);
    return temp;
}

public static int getLen(ListNode list) {
    ListNode iter = list;
    int len = 0;
    while (iter != null) {
        len++;
        iter = iter.next;
    }
    return len;
}

Answer 1

This section contains multiple Single Linked List Operation

import java.util.Scanner;
import java.util.Stack;

public class AddDigitPlusLL {

    Node head = null;
    int len =0;

    static class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    public void insertFirst(int data) {
        Node newNode = new Node(data);
        if (head != null)
            newNode.next = head;

        head = newNode;

    }

    public void insertLast(int data) {
        Node temp = head;
        Node newNode = new Node(data);
        if (temp == null)
            head = newNode;
        else {
            Node previousNode = null;
            while (temp != null) {
                previousNode = temp;
                temp = temp.next;
            }
            previousNode.next = newNode;
        }

    }

    public Long getAllElementValue() {
        Long val = 0l;
        Node temp=head;
        while(temp !=null) {
            if(val == 0)
                val=(long) temp.data;
            else
                val=val*10+temp.data;
            temp = temp.next;
        }

        System.out.println("value is :" +  val);
        return val;
    }

    public void print(String printType) {
        System.out.println("----------- :"+ printType +"----------- ");
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.data + "  --> ");
            temp = temp.next;
        }
    }

    public void generateList(Long val) {
        head = null;
        while(val > 0) {
            int remaining = (int) (val % 10);
            val = val/10;
            insertFirst(remaining);

        }
    }

    public void reverseList(Long val) {
        head =null;
        while(val >0) {
            int remaining = (int) (val % 10);
            val = val/10;
            insertLast(remaining);
        }
    }

    public void lengthRecursive(Node temp) {
        if(temp != null) {
            len++;
        lengthRecursive(temp.next);

        }
    }

    public void reverseUsingStack(Node temp) {
        Stack<Integer> stack = new Stack<Integer>();
        while(temp != null) {
            stack.push(temp.data);
            temp = temp.next;
        }

        head = null;
        while(!stack.isEmpty()) {
            int val = stack.peek();
            insertLast(val);
            stack.pop();
        }

        print(" Reverse Using Stack");
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner s = new Scanner(System.in);
        AddDigitPlusLL sll = new AddDigitPlusLL();
        sll.insertFirst(5);
        sll.insertFirst(9);
        sll.insertLast(8);
        sll.print("List Iterate");
        Long val = sll.getAllElementValue();
        System.out.println("Enter the digit to add");
        Long finalVal = val +s.nextInt();
        s.close();
        sll.generateList(finalVal);
        sll.print("Add int with List Value");
        sll.reverseList(finalVal);
        sll.print("Reverse the List");
        sll.lengthRecursive(sll.head);
        System.out.println("Length with Recursive  :"+ sll.len);
        sll.print("Before call stack reverse method");
        sll.reverseUsingStack(sll.head);
    }
}

Answer 2

The easiest way to reverse the single linked list is as follows.

private void reverse(Node node)
{
    Node current = Node;
    Node prev = null;
    Node next = null;

    if(node == null || node.next == null)
    {
        return node;
    }

    while(current != null)
    {
        next = current.next;
        //swap
        current.next = prev;
        prev = current;
        current = next;
    }
    node.next = current;
}

Answer 3

This can be done in O(n) time using O(1) space as follows:

• Reverse the entire list.
• Reverse the individual blocks.

Both can be done using something very similar to the standard way to reverse a singly linked-list and the overall process resembles reversing the ordering of words in a string.

Reversing only a given block is fairly easily done by using a length variable.

The complication comes in when we need to move from one block to the next. The way I achieved this was by having the reverse function return both the first and last nodes and having the last node point to the next node in our original linked-list. This is necessary because the last node's next pointer needs to be updated to point to the first node our next reverse call returns (we don't know what it will need to point to before that call completes).

For simplicity's sake, I used a null start node in the code below (otherwise I would've needed to cater for the start node specifically, which would've complicated the code).

class Test
{
   static class Node<T>
   {
      Node next;
      T data;
      Node(T data) { this.data = data; }
      @Override
      public String toString() { return data.toString(); }
   }

   // reverses a linked-list starting at 'start', ending at min(end, len-th element)
   // returns {first element, last element} with (last element).next = (len+1)-th element
   static <T> Node<T>[] reverse(Node<T> start, int len)
   {
      Node<T> current = start;
      Node<T> prev = null;
      while (current != null && len > 0)
      {
         Node<T> temp = current.next;
         current.next = prev;
         prev = current;
         current = temp;
         len--;
      }
      start.next = current;
      return new Node[]{prev, start};
   }

   static <T> void reverseByBlock(Node<T> start, int k)
   {
      // reverse the complete list
      start.next = reverse(start.next, Integer.MAX_VALUE)[0];
      // reverse the individual blocks
      Node<T>[] output;
      Node<T> current = start;
      while (current.next != null)
      {
         output = reverse(current.next, k);
         current.next = output[0];
         current = output[1];
      }
   }

   public static void main(String[] args)
   {
      //Scanner scanner = new Scanner(System.in);
      Scanner scanner = new Scanner("3 9 1 2 3 4 5 6 7 8 9\n" +
                                    "2 9 1 2 3 4 5 6 7 8 9");
      while (scanner.hasNextInt())
      {
         int k = scanner.nextInt();
         // read the linked-list from console
         Node<Integer> start = new Node<>(null);
         Node<Integer> current = start;
         int n = scanner.nextInt();
         System.out.print("Input: ");
         for (int i = 1; i <= n; i++)
         {
            current.next = new Node<>(scanner.nextInt());
            current = current.next;
            System.out.print(current.data + " ");
         }
         System.out.println("| k = " + k);
         // reverse the list
         reverseByBlock(start, k);
         // display the list
         System.out.print("Result: ");
         for (Node<Integer> node = start.next; node != null; node = node.next)
            System.out.print(node + " ");
         System.out.println();
         System.out.println();
      }
   }
}

This outputs:

Input: 1 2 3 4 5 6 7 8 9 | k = 3
Result: 7 8 9 4 5 6 1 2 3 

Input: 1 2 3 4 5 6 7 8 9 | k = 2
Result: 8 9 6 7 4 5 2 3 1 

Live demo.

Answer 4

Here is an iterative way of doing it... you read my full explanation here

Node reverseListBlocks1(Node head, int k) {
    if (head == null || k <= 1) {
        return head;
    }

    Node newHead = head;
    boolean foundNewHead = false;

    // moves k nodes through list each loop iteration
    Node mover = head;

    // used for reversion list block
    Node prev = null;
    Node curr = head;
    Node next = null;

    Finish: while (curr != null) {

        // move the mover just after the block we are reversing
        for (int i = 0; i < k; i++) {
            // if there are no more reversals, finish
            if (mover == null) {
                break Finish;
            }
            mover = mover.next;
        }

        // reverse the block and connect its tail to the rest of
        // the list (at mover's position)
        prev = mover;
        while (curr != mover) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // establish the new head, if we didn't yet
        if (!foundNewHead) {
            newHead = prev;
            foundNewHead = true;
        }
        // connects previous block's head to the rest of the list
        // move the head to the tail of the reversed block
        else {
            head.next = prev;
            for (int i = 0; i < k; i++) {
                head = head.next;
            }
        }
    }

    return newHead;
}