Brief explanation:
This is pretty straightforward question and most of interviewers would not be interested in asking this. However, this tests our basics of navigating a singly linked list.
Only point to remember here is, we need to keep track of "next", "previous" and "current" node at any point of navigation. We can use these nodes and alter links to change direction of list.
We will start current node set to start of the list, previous is set to NULL since there is nothing before first node. Note that previous node is not connected to "current" node before we start to alter the list.
For every node until it is not null:
- Connect "current" node to previous (next node is nothing but Current->Next) instead of "next" node. This is the major step where we break link between current to next but connect current to previous i.e. make
- Move current to next node,
- Move previous node to current node.
At the end of above loop, current node would have moved to end and "previous" node will be pointing to the first node of reversed list.
C# Code:
static void ReverseSinglyLinkedLists()
{
Node list = new Node()
{
data = 'm',
Next = new Node()
{
data = 'a',
Next = new Node()
{
data = 'n',
Next = new Node() { data = 'u', Next = null }
}
}
};
Node temp = list;
//Below code to print initial list
StringBuilder initial = new StringBuilder();
while (temp != null)
{
initial.Append(temp.data + " -> ");
temp = temp.Next;
}
initial.Append("NULL");
Console.WriteLine("Given Singly Linked List: " + Environment.NewLine + initial.ToString());
temp = list;
Node prev = null;
Node cur, next;
cur = list;
while(cur!=null)
{
next = cur.Next;
cur.Next = prev;
prev = cur;
cur = next;
}
//prev is now current first node on the revesed list
//Below code to print reversed list
StringBuilder reversedResult = new StringBuilder();
while (prev !=null)
{
reversedResult.Append(prev.data + " -> ");
prev = prev.Next;
}
reversedResult.Append("NULL");
Console.WriteLine("Reversed Singly List: "+ Environment.NewLine+ reversedResult.ToString());
}
No comments:
Post a Comment