Reversing a singly linked list in a single pass

Today I’d like to give codes and solution to reverse a singly linked list in a single pass and not using superfluous storage.

Off course there is a solution if you duplicate list, put all values into a vector or array, and other not efficient ways to accomplish this task. Recursive solutions could also be proposed. But iterative solution is the best way to solve this problem. Because if you use recursive method, there will be superfluous, and not necessary method calls and extra stack storage will be used for each local variables, and it won’t be best shot because if number of nodes in linked list is too much then you’ll probably exhaust your stack memory.

Continue reading

Spliting a singly linked list into two sub-lists from the middle node in one pass

This is a puzzle like problem for linked lists. We’ll use similar solution for our code in Finding The Half Of Linked List in Single Traversal. But we’ll add some spice to the code in order to convert solution to be applied to this problem.

Ok let’s have a look to our proposed solution. Continue reading

Finding The Half Of Linked List in Single Traversal

This is like a puzzle question: you iterate the list but at the end of the iteration (i.e. when you reach the end of linked list) you should display the half. The question seams hard because you do not know how many node exist in the list. So, how you find the half when you reach at the tail. One solution may be to store all elements into an array, but this is quite inefficient and possibly infeasible way to solve this question.

My proposed solution is:

  • Traverse the list with double next, this is iterating the list with node->next->next
  • Hold another pointer for half of the list. While iterating double next half of the list pointer iterates with one next.

I added the code for a simple list (supports addition to head, and tail – I did not test the tail :). Continue reading