# Fold a Linked List in Java

Hello coders ! Welcome Back to codingbroz where we help you learn coding concepts. Today we are here to discuss another coding interview problem on linked list data structure.

Today we are going to discuss a program to Fold a Linked List!

## Prerequisites :

Before moving towards solving this linked list problem to Fold a Linked List you need to have knowledge about two linked list concepts. These are as follows :

## Problem Statement :

You are given a linked list, you need to fold it and print it. e.g. If you are given a linked list : a -> b -> c -> d -> e -> f , then you need to reorder and fold the linked list in this order : a -> f -> b -> e -> c -> d

#### Input :

``1->2->3->4->5->6->7->null``

#### Output :

``1->7->2->6->3->5->4->null``

#### Sample Input :

``````10
5
1
4
6
9
9
6
4
1
5``````

#### Sample Output :

``5 5 1 1 4 4 6 6 9 9 ``

## Approach : Fold a Linked List

``````1. find the middle node
2. reverse the sub list from next of the middle node
3. connect the first node of sub list 1 with the first node of sub list 2
4. connect the first node of sub list 2 with the second node of sub list 1 and so on in a zig-zag manner.``````

## Program to Fold a Linked List :

```import java.util.*;

class Main {
public static class ListNode {
int val = 0;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}

while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;

}
return slow;
}

ListNode prev = null;
ListNode forw = null;

while(cur != null){
forw = cur.next;
cur.next = prev;
prev = cur;
cur = forw;
}
return prev;
}
public static void fold(ListNode head) {

mid.next = null;

ListNode f1 = null;
ListNode f2 = null;

while(c2 != null){
//backup
f1 = c1.next;
f2 = c2.next;
c1.next = c2;
c2.next = f1;
//move
c1 = f1;
c2 = f2;
}

}

static void printList(ListNode node) {
while (node != null) {
System.out.print(node.val + " ");
node = node.next;
}
}

public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
ListNode dummy = new ListNode(-1);
ListNode prev = dummy;
while (n-- > 0) {
prev.next = new ListNode(scn.nextInt());
prev = prev.next;
}

}
}```

The following solution is to fold a Linked List.

Now, Let’s talk about the time complexity of the given solution to Fold a Linked List!

Time Complexity : n + n/2 + n/2 = 2n

If we talk in terms of Big-O, then the time complexity of the code is O(n) and the space complexity of the code is constant [ O(1) ] as no extra space has been used.

#### More Interview Problems on Linked List

Today you learned How to fold a Linked List . Here are some more Coding Interview Problems on Linked List data structure you must try. These are as follows :

1. Check if a linked list is palindrome or not