© Parineeth M R

** Question 1. Reverse a linked list **

A linked list can be reversed without using recursion by maintaining 3 nodes: prev_node, cur_node and next_node. As we traverse the linked list, we update the 3 nodes and the links in the linked list are reversed. The time complexity is O(n).

## C/C++

/*Reverses the linked list without using recursion head: first node in the original linked list Return value: the first node of the reversed linked list */ struct node* reverse_linked_list(struct node *head) { struct node *cur_node, *prev_node, *next_node; cur_node = head; prev_node = NULL; while (cur_node) { /*Store the next node in a temporary variable*/ next_node = cur_node->next; /*Reverse the link so that current node points to the previous node*/ cur_node->next = prev_node; /*Update the previous node to the current node */ prev_node = cur_node; /*Proceed to the next node in the original linked list*/ cur_node = next_node; } /* Once the linked list has been reversed, prev_node will be pointing to the new head. So return it */ return prev_node; }

## Java

/*Reverses the linked list without using recursion head: first node in the original linked list Return value: the first node of the reversed linked list */ public static LinkedListNode reverseLinkedList(LinkedListNode head) { LinkedListNode curNode = head; LinkedListNode prevNode = null; while (curNode != null) { /*Store the next node in a temporary variable*/ LinkedListNode nextNode = curNode.next; /*Reverse the link */ curNode.next = prevNode; /*Update the previous node to the current node */ prevNode = curNode; /*Proceed to the next node in the original linked list*/ curNode = nextNode; } /* Once the linked list has been reversed, prevNode will have the new head. So return it */ return prevNode; }

## Python

#Reverses the linked list without using recursion #head: first node in the original linked list #Return value: the first node of the reversed linked list @staticmethod def reverse(head): cur_node = head prev_node = None while (cur_node): #Store the next node in a temporary variable next_node = cur_node.next #Reverse the link cur_node.next = prev_node #Update the previous node to the current node prev_node = cur_node #Proceed to the next node in the original linked list cur_node = next_node #Once the linked list has been reversed, prev_node will be #referring to the new head. So return it return prev_node