Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: `1->2->3->4->5`

For k = 2, you should return: `2->1->4->3->5`

For k = 3, you should return: `3->2->1->4->5`

(Java Code on Github at the bottom of the post. )

My thoughts and solution:

Q: What is the unknown?

A: To reverse nodes in a linked list k at a time and return the modified list.

Q: What are the data?

A: A linked list and an integer k.

Q: What are the constraints?

A: From the example above, we should probably assume this is a singly linked list. We cannot change the value in the node (Actually this is a very good idea in modifying linked list). Constant memory only. If at some point, the number of nodes is not the multiple of k, these nodes should remain the same order.

Q: Have you seen it before or at least something similar?

A: Yes I think I have. A similar problem is to reverse a singly linked list in place. I solved it before and it only took constant memory. I think we can apply the solution of that problem to each K nodes for reversing purpose.

Q: Good. For the whole problem, what kind of strategy should we use? Suppose we have reversed K nodes in the list, what about the rest of list?

A:  We do the same for the rest and connect with the k nodes reversed previously.

Q: Can you describe it in more details?

A: OK, for the rest of the linked list we reverse the nodes in k-Group and connect with previously reversed k nodes. Ah I see where this is heading. We are looking at a recursion here.

Q: Yes we are. Now think about the base case of this recursion.

A: That would be the number of remaining nodes is not a multiple of k and we should just connect them with the previously reversed part.

Q: What about the recursive case?

A: Hmm, we should reverse the current k nodes at hand. reverse the next k nodes and connect with them. Then return the current reversed part so the previously reversed part can connect with it.

Q: OK not super clear but I guess you have the idea.  In the base case, how do you determine if the number of remaining nodes is a multiple of k?

A: Starting from where we are, go k steps further. If at any point, we hit null, then we know there are enough nodes for reversal.

Q: Good. The take-away message here is that recursion could be a very handy trick for solving linked list related problems. So keep it in your toolbox.

Code on github:

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given `1->2->3->4->5->NULL`m = 2 and n = 4,

return `1->4->3->2->5->NULL`.

Note:
Given mn satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

Well, I did a similar question before, but that experience didn’t come to me immediately. So this is how I proceeded:

1. When I see reverse, I think about the Stack structure.
2. Reversing a linked list does not necessarily mean moving the whole node around. It may just require you to reverse the value in the node.
3. Moving the node somehow to reverse the list.

The question explicitly requires one pass and in-place, so idea No.1 is a no, but still valuable thought for other problems. I moved on to idea No. 2 and I got stuck for while. So maybe it is not the right direction for this question. OK, so move on to idea  No.3. I kept asking myself this question: have you seen it before? Then suddenly something came up: I solved a question of reversing a whole list in-place and one pass before. And this question is just a more general version.

Say we have a list:

N1 -> N2 -> N3 -> NULL

If we reverse the whole list, it becomes:

N3 -> N2 -> N1 -> NULL

OK. to get N1 -> NULL is easy, we just set N1.next = NULL. What about N2 -> N1 ? The same, we set N2.next = N1. Wait! How do we get to N2? Eh, N2 = N1.next. But did we just set N1.next = NULL? So we won’t be able get N2 now, unless we save the reference to N2 somewhere else before setting N1.next = NULL.

```Node current = N1;
Node previous = NULL;

Node nextNode = current.next;
current.next = previous;
previous = current; //previous points to N1;
current = nextNode; //current points to N2;
```

I hope you get the idea. This code snippet should be wrapped in a loop to process the whole list. But knowing this does not make things easier. The corner cases can be tricky and it took me a while to make sure the answer was bug-free. Do it manually, not in any IDE.

Things to check:

• when there is only one node in the list.
• when m = 1
• when m == n

Code on github:

Detect the first node of the cycle in a singly-linked list

If a singly-linked data structure contains a cycle, determine the first node that participates in the cycle. you may use only a constant number of pointers into the list (and no other variables). The running time of your algorithm should be linear in the number of nodes in the data structure. You are given the pointer to the first node of the list.

(Java Code on github at the bottom of the post. )

My thoughts and solutions:

This is the third time I encountered this question and once again, failed. Well I remembered how to write the code, but I couldn’t figure out the complete reasoning, which made the code kind of useless. Memorizing the code is never my intention but it seems that my brain disagrees…The following is a conversation:

Q: What is the unknown? What are the data? Any conditions or constraints?

A: The unknown is the where the cycle begins. The data is a pointer to the first node of the list. The constraints are that we can only use constant numbers of pointers and the running time should be linear.

Q: Have you seen a similar question before? If yes, can we use its result or method here?

A: Yes, a similar question is to detect if a cycle exists. Hmm, we used a fast runner and slow runner approach. I guess it’s a common strategy to use when dealing with cycles. So we can still consider using it here.

Q: Describe the approach above.

A: We have two pointers F and S, with S moving at rate 1 and F moving at rate 2.

Q: OK, can we introduce a symbol for our unknown? Quantify it?

A: Sure, suppose that node is k steps away from the first node of the list.

Q: Now suppose S moved k steps, where are F?

A: In that case, S is at that starting node of the cycle while F is k steps into the cycle because F moved 2k steps when S moved k steps.

Q: Relatively speaking, what’s the location of F according to S and vice-versa?

A: Then S is k steps behind F and F is CYCLE_SIZE – k steps behind S.

Q: What if k is bigger than CYCLE_SIZE?

A: Hmm, then we can replace k with K = k % CYCLE_SIZE. Whether k or K steps into the cycle points to the same node.

Q: Good, now rephrase the answer to the relative location question.

A: OK, S is K steps behind F and F is CYCLE_SIZE – K steps behind S.

Q: If F and S keep moving, they will meet somewhere in the cycle. When and where will they meet?

A: Aha, suddenly it looks like a junior high physics question…F will catch up S at a rate of 1. So after CYCLE_SIZE – K unit times, they will meet. Since at the beginning S is at entrance of the cycle, after CYCLE_SIZE – K time, S is CYCLE_SIZE – K steps into the cycle. Hmm so when F and S meet, they are simply K steps behind the entrance of the cycle.

Q: Great. Now who else is K steps behind the entrance of the cycle besides F and S?

A: Eh, no one?

Q: OK look at our data. Did we use all the data?

A: Eh the data is the first node of the list. Hmm, but it’s k steps from the cycle…

Q: What’s the relationship between k and K?

A: Oh right, K = k % CYCLE_SIZE. In the cycle, K and k are interchangeable. So F, S and the first node of the list are all k steps behind the cycle! If now we start from the first node of the list with a pointer T and keep move, the place where S and T meet is our answer!

Q: You got it.

Summary:

• Locate the unknown. Symbolize and quantify it!
• When dealing with loops or cycles, think about multiple pointers with different moving rates.
• In this catch and run problem, ask both when and where.
• In a cycle, K (= k % CYCLE_SIZE) and k steps into the cycle point to the same node.
• To find a location, imagine how you get there and when you get there, what are other things like? (when S is at the entrance of the cycle, where is F?)

Code on github:

Delete a middle node from a singly linked list with only the access to this node—A conversation

Algorithm is one the fundamental components that a programmer should master. But every time I read a book about it, I see intrusive instructions about how to solve a problem using several algorithms. Well they just tell you that you should use this and that. Sure, they are brilliant ideas, but how do those ideas come up? If we do not know this process, it is hard to say we have really learned.

I’ve been reading the book “How to solve it” by George Pólya. It is a great book that shows you how to approach a problem using various steps. You can ask about certain questions and answer them to get a better chance to obtain the final solution. Although this book is about mathematics, I think it also applies for algorithms or even just problems in general. So I’d like to write the conversation I made myself to show the process of how we get an algorithm without giving intrusive instructions. These are just my humble ideas and suggestions are always welcome.

====================================================================

Q: What is the unknown? What is our goal?

A: Eh a way to delete a node in a linked list.

Q: What are the data?

A: A node and a linked list.

Q: What are the conditions and restrictions?

A: The list is singly linked. The node is in the middle of the list. And we only have access to the node to delete.

Q: What does it mean by singly linked?

A: It means the node only knows which node is the next but not the one precedes it.

Q: What does it mean by in the middle?

A: It means the node is not the head or the tail of the linked list.

A: Eh I guess it means we do not have access to the head of the list…only the node we want to delete is provided…man this is impossible!

Q: Why do you think it is impossible?

A: Well, to delete a node in a singly linked list, we have to know which node precedes it at least. That means we need to know the head node…

Q: Well the head is not provided.  Let’s forget about the restriction and look at an example. Can you think of an example of deleting a middle node from a singly linked list?

A: Sure. Say we have a->b->c->d->e->null and we want to delete c.

Q: So what does the linked list looks like after the deletion?

A: a->b->d->e->null.

Q: Is there any other way other deletion you can use to get this result?

A: ….

Q: What are the differences between these two lists? (Comparison side by side!)

a->b->c->d->e->null

a->b->d->e->null

A: Well their lengths are different. Actually I don’t think we know what precedes c. So I would write the lists like the following:

x->x->c->d->e->null;

x->x->d->e->null;

Q: You got a point. We should only focus on things after c. Maybe I should ask a different question. Are there any differences for node d and e before and after the deletion?

A: I don’t know. Their values stay the same…wait, but their position changed after the deletion.

Q: You mentioned the value in the node. So deleting a node means…?

A: That we don’t want this value any more.

Q: Think about these two factors: value, and position shift…node can shift. What about value?

A: Eh we can shift the value too…Ah right instead of shifting the nodes…So I just need to copy the value of the nodes following c to the previous nodes and delete the last node…

Q: Correct.

A: Orz…OK.

Q: Yeah I know it may not come into your mind at first glance. The restrictions confine your mind. Compare the example before and after an operation. Think about different ways to achieve the same effect.

Features of a LinkedListNode: data, next node and position!

Link to the code on github (You will need the first one to run the second one):