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**

Contents

**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; } } public static ListNode midNode(ListNode head){ if(head == null || head.next == null) return head; ListNode slow = head, fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } public static ListNode revList(ListNode head){ if(head == null || head.next == null)return head; ListNode cur = head; 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) { if(head == null || head.next == null)return; ListNode mid = midNode(head); ListNode nHead = mid.next; mid.next = null; nHead = revList(nHead); ListNode c1 = head; ListNode c2 = nHead; ListNode f1 = null; ListNode f2 = null; while(c2 != null){ //backup f1 = c1.next; f2 = c2.next; //linking 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; } ListNode head = dummy.next; fold(head); printList(head); } }

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 :

**Check if a linked list is palindrome or not****Unfold a Linked List****Merge Two sorted Linked list****Merge Sort a Linked List****Remove Nth from end of linked list****Segregate even and odd nodes in a linked list**