Reverse a linked list from position m to n. Do it in-place and in one-pass.
1->2->3->4->5->NULL, m = 2 and n = 4,
Given m, n 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:
- When I see reverse, I think about the Stack structure.
- 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.
- 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: