How to cancel a singly linked list in blocks of a certain size in O (n) time?

Question

I recently ran into an algorithm problem:

Flip the singly linked list in k blocks in place . An iterative approach is preferred. The first block of the resulting list must be maximum with respect to k. If the list contains n elements, the last block will either be filled 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 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 can be done O (n) times using O (1) space as follows:

• .
• .

- , .

.

, . , , , , node node . , node , node ( , ).

null start node ( node, ).

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();
      }
   }
}

:

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 

.

Answer 2

...

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 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 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;
}

Answer 3

The easiest way to flip one 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 4

This section contains several operations with one linked list.

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);
    }
}