Java Program to fold a Linked List

June 25, 2020

Java Program for folding a given Linked List

Java Program for folding a given Linked List . It is a user defined or user input program. To fold a linked list we have to first create a simple linked list. When we fold a linked list it will take place between the nodes. We can say that at every step we change the next of the left node such that it points to the right node. the next of a right node also change accordingly.

Java Program for folding a given Linked List . Example:

Given Linked list : 1–>2–>3–>4–>5–>6

Output of the given linked list after folding

1–>6–>2–>5–>3–>4

Algorithm

We have used recursion here.

There will be three parameters to the recursive function : left node, right node and the floor. Floor basically represents the level of recursion.
We have kept the left node in heap section. Because when we fall one level in recursion then right node is automatically adjusted but we need to make change in left so that it points to the next node now. If it would be in stack frame, the changes we make to the start will go with the recursion level. And we would be at same left node again. For the changes to be there, we keep the left node in heap. Doing so, changes made in the left node always remain as it is even if we fall one level in recursion.
At every step, we change the next of the left node such that it points to the right node. The next of the right node is also changed accordingly.
Move the left node by one. The changes are made in heap and not in stack frame.
We do step 3 and 4 until the floor > half of the size of linked list.
When floor is equal to half of the size of linked list, make right node as new tail and change its next to null.

Java program for folding a Linked List

import java.util.*;

public class PrepInsta
{

  public static void main (String[]args) throws Exception
  {
    LinkedList ll = new LinkedList ();
      ll.addFirst (50);
      ll.addFirst (40);
      ll.addFirst (30);
      ll.addFirst (20);
      ll.addFirst (10);

      ll.display ();

      ll.fold ();

      ll.display ();
  }

}

class Fold_LinkedList
{
  private class Node
  {
    int data;
    Node next;

// Node constructor
// There are two fields in the node- data and address of next node
    public Node (int data, Node next)
    {
      this.data = data;
      this.next = next;
    }
  }

  private Node head;
  private Node tail;
  private int size;

// Linked list constructor
  public LinkedList ()
  {
    this.head = null;
    this.tail = null;
    this.size = 0;

  }

// Function to find the size of linked list
  public int size ()
  {
    return this.size;
  }

// Function to check whether linked list is empty or not
  public boolean isEmpty ()
  {
    return this.size () == 0;
  }

// Function to traverse and print the linked list
  public void display ()
  {
    Node temp = head;
    while (temp != null)
      {
	System.out.print (temp.data + "  ");
// Set temp to point to the next node
	temp = temp.next;
      }
    System.out.println ("END");
  }

// Function to add a node in beginning of linked list
  public void addFirst (int item)
  {
// Create a temp node which points to head
    Node temp = new Node (item, head);

// If linked list is empty, temp is the head and tail node both
    if (this.size == 0)
      {
	this.head = this.tail = temp;
      }

// else set the head such that it now points to temp node
    else
      {
	this.head = temp;

      }

    this.size++;
  }

  public void fold ()
  {
    HeapMover left = new HeapMover ();
    left.node = this.head;
    this.fold (left, this.head, 0);

  }

//Function to fold the linked list
  private void fold (HeapMover left, Node right, int floor)
  {

//Base case is when we reach end of linked list
    if (right == null)
      {
	return;
      }

//Recursive calls
    this.fold (left, right.next, floor + 1);

//Till floor is greater than 1/2 * size of linked list
    if (floor > this.size () / 2)
      {

	Node temp = left.node.next;
	left.node.next = right;
	right.next = temp;

	left.node = temp;
      }

//To set the tail of linked list
    if (floor == this.size () / 2)
      {
	this.tail = right;
	this.tail.next = null;
      }

  }

//Class to keep a node in the heap
  private class HeapMover
  {
    Node node;
  }

}

Output
Given Linked List
10-->20-->30-->40-->50
Linked lis after folding
10-->50-->20-->40-->30