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 :

  1. Find Middle of a linked list
  2. How to reverse a linked list

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 :

  1. Check if a linked list is palindrome or not
  2. Unfold a Linked List
  3. Merge Two sorted Linked list
  4. Merge Sort a Linked List
  5. Remove Nth from end of linked list
  6. Segregate even and odd nodes in a linked list

Leave a Comment

Your email address will not be published. Required fields are marked *