Fold Linked List

Problem Statement:
            Fold the given Linked List

Solution:

Download Source Code

As a Scarf is folded , the above linked list is also folded and merged.

The recursive Logic in-order to achieve this is given below. I would recommend you to
 try it yourself and also refer to Check Pallindrome List , which involves similar logic.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

public static Node foldList(Node head) { return fold(head, head); } /** * Linked List Folding Sub-routine * @param head: head pointer * @param curr: current pointer * @return: head of the folded list */ private static Node fold(Node head, Node curr) { if (curr == null) return head; Node result = fold(head, curr.next); // condition to stop execution if result is head and curr is not the // last node if (result != head || curr.next == null) { // handling odd and even number of nodes if (result != curr && result.next!=curr) { curr.next = result.next; result.next = curr; return curr.next; } curr.next = null; } return head; }

Please comment and post your suggestions , any suggestion for enhancing the solution is most-welcome.

Happy Coding !! :)