13 Apr 2014

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 !! :)

15 comments:

  1. Hello Prateek

    The Algorithm mentioned above fails when number of node in input list is Even...

    Providing a recursive alternative Algorithm

    private Node lastNode(Node node){
    Node prev = null;
    if(node.next == null){
    return null;
    }
    while(node.next != null){
    prev = node;
    node = node.next;
    }
    prev.next = null;
    return node;
    }

    public Node foldLinkList(Node node){
    if(node != null){
    Node lastNode = lastNode(node);
    Node returnNode = foldLinkList(node.next);
    if(returnNode!=null || lastNode!=null){
    node.next = lastNode;
    lastNode.next = returnNode;
    }else{
    node.next = returnNode;
    }
    return node;
    }else{
    return node;
    }
    }

    ReplyDelete
    Replies
    1. Hi Ashis,
      Thanks for investing your time to find that flaw for even number of nodes.
      I have updated the code.
      I think you can work on the code that you have provided
      1. Complexity is O(n^2)
      2. number of lines of code can be reduced.

      Delete
  2. Hello Prateek
    The revised algo look good...
    cheers

    ReplyDelete
  3. From small, mom and pop shops every one of the way through to heavily established market
    leaders, each year businesses in every industry
    and also every size decide to participate over these important
    promotional events. Or you might simply have information on a related field that the target audience would find interesting.
    In short, it's crucial for organizations to make certain they deliver enough exciting details to pique the crowd's interest without crossing the queue into the dreaded information overload territory.


    Also visit my blog post ... inexpensive pop up booth displays

    ReplyDelete
  4. Some birds, for instance will take part in singing displays that mirror the motions from the grass display much like the Cutthroat finch.
    If you already possess a trade show booth designed,
    understand it ready for the full analysis. Visit your customers' Facebook pages
    and personally invite these phones stop by and visit your trade
    exhibition displays and banner stands.

    Here is my web site; inexpensive exhibits displays

    ReplyDelete
  5. Some birds, for example will take part in singing
    displays that mirror the motions of the grass display such as the
    Cutthroat finch. To my thoughts there is nothing more standard or spontaneous than arranging fresh flowers
    in the vase. Also, checking in with the business running the wedding can provide additional information on whom to use and whether you will find discounts provided to participating businesses.



    Here is my web page - modular trade show display

    ReplyDelete
  6. Some birds, for instance will embark on singing displays that mirror the motions of the grass
    display much like the Cutthroat finch. If you already
    possess a display booth designed, get it ready for a
    full analysis. This is caused by a number of elements which
    feature strongly during these LED signs.

    Look into my web page: buy velcro display panels

    ReplyDelete
  7. Hmm is anyone else having problems with the
    pictures on this blog loading? I'm trying
    to find out if its a problem on my end or if it's the blog.
    Any responses would be greatly appreciated.


    my site :: blog content

    ReplyDelete
  8. Hello there! Quick question that's entirely off topic. Do you know how to
    make your site mobile friendly? My blog looks weird when browsing from my iphone4.

    I'm trying to find a template or plugin that might be able
    to correct this problem. If you have any recommendations, please share.
    Many thanks!

    my blog post Las Vegas Kitchen Appliance Repair

    ReplyDelete
  9. I every time spent my half an hour to read this webpage's articles everyday along with a mug of coffee.


    my website - hire a private jet prices

    ReplyDelete
  10. Hi there! I simply want to offer you a big thumbs up for the excellent
    information you have right here on this post. I will be coming back to your
    blog for more soon.

    My web page; best wrinkle eye cream

    ReplyDelete
  11. What's up to all, it's actually a fastidious for me to visit this web
    site, it contains helpful Information.

    Also visit my web-site - private jet london

    ReplyDelete
  12. Hi, i think that i saw you visited my blog so i came to “return the favor”.I'm attempting to find
    things to enhance my website!I suppose its ok to use some of your ideas!!


    Feel free to visit my web-site: charter flight cost

    ReplyDelete
  13. Great blog! Is your theme custom made or did you download it from somewhere?
    A design like yours with a few simple tweeks would really make my blog shine.
    Please let me know where you got your theme.
    Thanks a lot

    my webpage: google search engine

    ReplyDelete