Reverse a Linked List Editorial

Practice Problem Link: Reverse A Linked List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a linked list, reverse it.

Approach

The idea is to traverse the linked list and reverse the pointer for each node.

• Initialize three pointers: currentNode as head, prevNode as NULL and nextNode as NULL.
• Traverse the linked list. While currentNode is not NULL, reverse the pointer for each node to its previous node.
• Finally, change the head pointer.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
public:
	int data;
	ListNode* next;

	ListNode(int data) {
		this->data = data;
		this->next = NULL;
	}
};
*/

ListNode* reverseLinkedList (ListNode* head) {
    ListNode* currentNode = head, *prevNode = NULL, *nextNode = NULL;
	while(currentNode != NULL) {
		nextNode = currentNode->next;
		currentNode->next = prevNode;
		prevNode = currentNode;
		currentNode = nextNode;
	}
	head = prevNode;
	return head;
}

Java

// class ListNode {
// 	int data;
// 	ListNode next;

// 	ListNode (int data) {
// 		this.data = data;
// 	}
// }

class Solution {
	ListNode reverseLinkedList (ListNode head) {
		ListNode currentNode = head, prevNode = null, nextNode = null;
		while(currentNode != null) {
			nextNode = currentNode.next;
			currentNode.next = prevNode;
			prevNode = currentNode;
			currentNode = nextNode;
		}
		head = prevNode;
		return head;
	}
}