# Java Program to fold a Linked List

## 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:

Output of the given linked list after folding

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

We have used recursion here.

1. There will be three parameters to the recursive function : left node, right node and the floor. Floor basically represents the level of recursion.
2. 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.
3. 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.
4. Move the left node by one. The changes are made in heap and not in stack frame.
5. We do step 3 and 4 until the floor > half of the size of linked list.
6. 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
{

ll.display ();

ll.fold ();

ll.display ();
}

}

{
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 tail;
private int size;

{
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 ()
{
while (temp != null)
{
System.out.print (temp.data + "  ");
// Set temp to point to the next node
temp = temp.next;
}
System.out.println ("END");
}

{
// 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)
{
}

// else set the head such that it now points to temp node
else
{

}

this.size++;
}

public void fold ()
{
HeapMover left = new HeapMover ();

}

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

}```
```OutputGiven Linked List10-->20-->30-->40-->50Linked lis after folding10-->50-->20-->40-->30
```