Given a Linked list, the task is to print a singly linked list in a spiral fashion. Starting from the first node then the last node followed by the second node and then the second last node, continuing this pattern until the entire linked list is traversed. for example:
Input:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> X
Output:
1 -> 6 -> 2 -> 5 -> 3 -> 4 -> X
Input:
1 -> 2 -> 3 -> X
Output:
1 -> 3 -> 2 -> X
I tried making array list and by using two pointers approach to print this solution but it did not work. Can anyone please explain any better approach for the same.
Assuming a program defined single linked list class, you could create a vector of pointers to each node in the list, in which case the spiral pattern is simple. I'm not sure if that is the intended goal.
It's possible that the intended goal operates directly on the list. One method would be reversing the list as you traverse through the list. You'll need four main pointers, first node of list, last node of list, one for scanning | reversing forwards, one for scanning | reversing backwards, until the pointers meet, and pointers needed to traverse | reverse a section of the list. When done, you'll need to "unreverse" the right half of the list, starting from pointer to last node of list.
Another option would be to convert the list to an XOR list, where each nodes link is the XOR of the pointers to the previous and next nodes. This results in the equivalent of a doubly-linked list, but requires "iterators" with two pointers, one to "previous" node, one to "current" node. When done, the list would be converted back to a normal single linked list.