Suppose given singly linked list: Head -> 5- > 2 -> 3 -> 1 -> null I want to reverse it like: Head -> 1 -> 3- > 2 -> 5 -> null
Category: Data Structure And Algorithms | Tags: C#, Java, C++ Programming, Interview Question |
Suppose given singly linked list: Head -> 5- > 2 -> 3 -> 1 -> null I want to reverse it like: Head -> 1 -> 3- > 2 -> 5 -> null
Answers:
Given linked list is a singly list suppose Node structure is:
Now we write method to reverse linked list:
To reverse a singly list we needed three pointers pre, current and next. First we start from head and copy head reference (value = 5 in our scenario) in current, Next node(2 in our scenario) we copy in next pointer, now we have to reverse where we have to make current pointer's next pointer to previous node, because 5 is head so we have to make its next pointer null in order to reverse(but for 2->3 we make it 2<-3 in next iteration) so we set current.Next pointer to pre. again we copy current node pointer in pre for next iteration. And in last line of loop we set current as next so now current is node which value=2 and so on. Let's see it how it works, suppose we have AddNode and Traverse methods to add nodes and print nodes, we can see output by running code:
Output: Sequence of nodes: 5 2 3 1 Sequence of nodes after reversing: 1 3 2 5
To learn linked lists in detail refer link: https://www.dotnetlovers.com/Article/145/implementation-and-analysis-of-linked-list-data-structure