According to the general view, the subject/notes on linked list :-
A singly linked list whose nodes contain two fields: an integer value and a link to the next node
=>Here we have both an iterative and a recursive solution for this problem.
let this is the example
This is an exception for the head node, and can be done outside the while loop.
But, before we do this we will need a temp variable to point to the 2nd node (the node after the head node), because the only way to reference the 2nd node is through the head node’s next pointer.
2. The 2nd node (the node after the head node) should have it’s own next pointer changed to point to the head node. This will reverse the order of the nodes. But, remember that the 2nd node’s next pointer will at first be pointing to the 3rd node. This means that before we change the 2nd node’s next pointer, we have to save a reference to the 3rd node otherwise we will have no way of referencing the 3rd node. So, we simply store a reference to the 3rd node in a variable before we change the 2nd node’s next pointer.
3. The 3rd node then becomes the “first” node in the while loop and we repeat the process of changing pointers described in step 2.
4. Continue step 3 until we come across a node that has a next pointer set to NULL. When we do come across a NULL next pointer we just set the head node to point to the node that has the NULL next pointer. This node was previously the tail node, but is now the head node because we are reversing the linked list.
Singly linked list
Singly linked lists contain nodes which have a data field as well as a 'next' field, which points to the next node in line of nodes. Operations that can be performed on singly linked lists include insertion, deletion and traversal.
A singly linked list whose nodes contain two fields: an integer value and a link to the next node
=>Here we have both an iterative and a recursive solution for this problem.
Reverse a linked list iteratively
Let’s assume that we are going to start reversing the linked list
starting from the very first node – the head node.
Reverse a linked list iterative algorithm
1. The head node’s next pointer should be set to NULL since the head will become the tail.let this is the example
This is an exception for the head node, and can be done outside the while loop.
But, before we do this we will need a temp variable to point to the 2nd node (the node after the head node), because the only way to reference the 2nd node is through the head node’s next pointer.
2. The 2nd node (the node after the head node) should have it’s own next pointer changed to point to the head node. This will reverse the order of the nodes. But, remember that the 2nd node’s next pointer will at first be pointing to the 3rd node. This means that before we change the 2nd node’s next pointer, we have to save a reference to the 3rd node otherwise we will have no way of referencing the 3rd node. So, we simply store a reference to the 3rd node in a variable before we change the 2nd node’s next pointer.
3. The 3rd node then becomes the “first” node in the while loop and we repeat the process of changing pointers described in step 2.
4. Continue step 3 until we come across a node that has a next pointer set to NULL. When we do come across a NULL next pointer we just set the head node to point to the node that has the NULL next pointer. This node was previously the tail node, but is now the head node because we are reversing the linked list.
No comments:
Post a Comment