8 Nov 2013

Reverse Linked List in Chunks

Problem Statement:
                   Reverse a given linked list in chunks of given size.

Given below is the linked list which is reversed in chunks of size 3.

Solution : 

The above problem can be solved both by 
  1. Recursion 
  2. Iteration

Full Source Code: LINK

1. Below is recursive implementation: 
       The below sub routine use a another sub-routine which helps in reversing the list of the chunk size.

public Node reverseInchunks(Node root, int k){

  if(root==null)
   return null;

  Node first=root;
  Node current=first;

  int count = k-1;
  while(current.next!=null && count > 0)
  {
   current=current.next;
   count--;
  }

  Node  last=reverseInchunks(current.next,k);
  current.next=null;
  
  Node subHead=reverse(first);

  first.next=last;

  return subHead;
 }

 public Node  reverse(Node head) {

  Node result;
  if(head.next ==null) 
   return head;

  result = reverse(head.next);

  head.next.next = head;

  head.next = null;

  return result;
 }

  
2. You can also be asked to reverse the list iteratively, below is the solution.

  public Node reverseChunkIterative(Node head, int k){

  if(head==null)
   return null;
  
  Node first, previous,last;
  first= previous=last=null;
 
  Node current=head;
  
  while(current!=null){
   

   Node temp=current; 
   previous =null;
   Node next=null;
   int count =k;
            
   while(current!=null  && count>0){
    next = current.next;
    current.next = previous ;
    previous = current ;
    current = next;
    count--;
   }
   
   if(first == null)
    first = previous;
   else
    last.next=previous;

   last=temp;
  }
  return first;
 }

 
For the simulation of the above procedures on ideone.com follow the link given above.
Thanks to Rohit Jain for suggesting the recursive solution.

Your suggestions, queries , critiques are most welcome , feel free to comment.

Happy Coding !! :)

22 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Please explain to me one thing. You are not explicitly changing the head pointer of the linked list. How does it manage to change after reversing first k nodes?

    ReplyDelete
    Replies

    1. Applogies for the delay , the comment went unnoticed,
      Explanation:
      1. Recursive Case:
      The variable "subHead" is returned in reverse manner of the linked list.
      So if u consider the chunk 4-> 5-> 6 , for the example given above
      here 'first' = 4 , last = '7' and 'subhead' = 6 , all this is done in the reverse manner ,
      this 'subhead' becomes 'last' for the chunk 1->2->3 , and here
      'first' =1 ; 'last' = 6 and 'subhead'=3
      so when the subroutine call is over u get last element of the first chunk, that is "3" is returned as the 'subhead'
      which is nothing but the new head of the linked list in the above example.

      2. Iterative Case:
      This is pretty and u must have already figured it out,
      i have taken a pointer 'first' which is initially null, and after reversal of the
      first chunk 1->2->3 "first" pointer is updated.

      Delete
  3. I love reading through a post that can make people think.
    Also, thanks for allowing me to comment!

    my blog post :: best private jet charter companies

    ReplyDelete
  4. It's perfect tkme to make a few plans for the longer
    term and it is time to bee happy. I've learn this put up and if I
    mayy just I desire to recommend you ffew fascinating issues or suggestions.
    Maybe you can write subsequent articles relating to this article.
    I want to learn moee things approximately it!

    Here is myy web blog Las Vegas Appliance Repair

    ReplyDelete
  5. Hi, I would like to subscribe for this weblog to get latest
    updates, therefore where can i do it please help out.



    Here is my page ... solicitor negligence claims

    ReplyDelete
  6. First off I want to say awesome blog! I had a quick
    question in which I'd like to ask if you don't mind. I was interested to know
    how you center yourself and clear your thoughts before writing.
    I've had difficulty clearing my mind in getting my ideas out
    there. I do take pleasure in writing but it just seems like the first
    10 to 15 minutes are lost just trying to figure out how to begin. Any ideas or hints?

    Cheers!

    My blog post: expert refutes

    ReplyDelete
  7. I think this is among the most vital information for me.

    And i'm glad reading your article. But want to
    remark on few general things, The web site style is wonderful, the articles is really excellent :
    D. Good job, cheers

    Here is my weblog :: job agencies in london

    ReplyDelete
  8. I'm truly enjoying the design and layout of your site.
    It's a very easy on the eyes which makes it much more enjoyable
    for me to come here and visit more often. Did you hire out a designer to create
    your theme? Outstanding work!

    Feel free to visit my web-site ... entry level social media jobs

    ReplyDelete
  9. My spouse and I absolutely love your blog and find many of your post's to be just what I'm looking for.
    Does one offer guest writers to write content available for you?

    I wouldn't mind producing a post or elaborating on many of the subjects
    you write about here. Again, awesome blog!

    Also visit my web-site: new tefal

    ReplyDelete
  10. Hiya very nice site!! Man .. Beautiful .. Amazing .. I will
    bookmark your web site and take the feeds additionally?
    I am glad to find so many helpful information right here within the submit,
    we want develop extra strategies in this regard, thanks for sharing.

    . . . . .

    Here is my web blog - medical negligence solicitors

    ReplyDelete
  11. Undeniably believe that which you stated. Your favorite justification appeared to be on the net the easiest thing to be
    aware of. I say to you, I definitely get annoyed while people consider worries that they
    just don't know about. You managed to hit the nail upon the top and defined out the
    whole thing without having side-effects , people
    can take a signal. Will likely be back to get more.
    Thanks

    Feel free to visit my webpage private jet rates

    ReplyDelete
  12. Incredible quest there. What happened after? Take care!

    Also visit my site - export a car

    ReplyDelete
  13. Heya! I'm at work surfing around your blog from my new iphone 3gs!
    Just wanted to say I love reading your blog and look forward to all your posts!
    Carry on the superb work!

    my website :: charter flights from uk

    ReplyDelete
  14. Attractive part of content. I just stumbled upon your website and in accession capital to claim that I acquire
    actually loved account your weblog posts. Anyway I will be subscribing in your augment and even I achievement you access constantly rapidly.


    Also visit my web site; sell houses fast

    ReplyDelete
  15. Write more, thats all I have to say. Literally, it seems
    as though you relied on the video to make your point.
    You definitely know what youre talking about, why waste your
    intelligence on just posting videos to your weblog when you could be giving us something informative to read?


    Feel free to surf to my web blog; seo service provider

    ReplyDelete
  16. There's definately a great deal to know about this issue.
    I love all of the points you have made.

    Take a look at my site ... company name search

    ReplyDelete
  17. Hey just wanted to give you a quick heads up. The text in your article seem to be running off the screen in Internet explorer.
    I'm not sure if this is a format issue or something to
    do with internet browser compatibility but I thought I'd post to
    let you know. The design look great though! Hope you get the
    problem resolved soon. Cheers

    Feel free to visit my webpage buy a house london

    ReplyDelete
  18. Reversing a linked list in chunks introduces complexity to a classic data structure. Is Bad Games Breaking the list into segments and reversing them requires intricate pointer manipulation.

    ReplyDelete