Reverse a Singly Linked List

Problem: reverse a singly linked list.

Three cases:

1. Acyclic list
2. Completely cyclic list (all nodes are in the cycle/loop)
3. Partially cyclic list (at least one node not in the cycle/loop)

This post discusses Case 3.
Case 3 is some different from Case 1 and Case 2. In some sense, we cannot give an algorithm that will for sure do what you want.

Attempt 1:
Since the first node (starting from head) in the cycle has 2 incoming pointers and 1 outgoing pointer, if we literally reverse every link in the list, this will violate the nature of singly linked list. Actually, there is no sufficient pointer fields to record necessary information.

Attempt 2:
If we define the node whose next points to the first circular node as the tail node of the list, and simply ignore the link from it to the first circular node, we will break the cycle and return a general acyclic list. In addition, more memory will be needed to test if it reaches some node that has appeared before.

Attempt 3:
If simply follow the procedure for reversing an acyclic list as in Case 1, there won't be any error in the running. The problem following is that not all links in the list are reversed, since those links before the loop will be reversed twice, and as a result, unchanged.

Personally, the problem for this case is still open. People may feel Attempt 3 would be the best. But not perfect either!

Related Posts:

Discussion about Case 1

Discussion about Case 2