Reverse a Linked List

© 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