How to traverse linked list in c++?

Given a pointer to any node, what is the optimum no.of nodes you need to traverse to find the sorting order in a sorted circular-singly-linked list?

• Answer:

  Assume the size of list as N( just for the sake of explanation ). Traversing 3 nodes is sufficient. 2 is not sufficient because of Case 2 and Case 3 explained below. Let the 3 elements traversed are a, b, and c. Case 1 : Given pointer points to one of the first N - 2 elements in the sorted order. Then the 3 elements will be in the original sorted order. If a < b < c, sorted order is ascending( non-decreasing ), otherwise it is descending(non-increasing). Case 2 : Given pointer points to the last element in the sorted order. Then the last two elements of the traversed 3 elements will be in the original sorted order. If b < c, sorted order is ascending(non-decreasing), otherwise it is descending(non-increasing). Case 3 : Given pointer points to last but one element in the sorted order. Then the first two elements of the traversed 3 elements will be in the original sorted order. If a < b, sorted order is ascending(non-decreasing), otherwise it is descending(non-increasing). But, the question is how do we find out where the pointer points to? ( to last element or last but one element or none of these two ). Step 1 : If a < b < c or a > b > c, pointer points to one of the first N - 2 elements. If not, go to step 2 Step 2 : If a > b < c < a or a < b > c > a, pointer points to the last element. If not go to step 3. Step 3 : If a < b > c < a or a > b < c > a, pointer points to the last but one element Note : This explanation is for the list containing no duplicates, but, it is trivial to expand it for the list with duplicate elements too. Instead of traversing 3 elements, traverse till we get 3 distinct elements.