700005. Reverse a linked list
Easy
Reverse a linked list
Summary
Reverse a singly linked list. A singly linked list is defined as follows: Each element in the linked list contains a data field to hold the integer value stored in the node and a reference (i.e., "link") part that points to the next node in the sequence of nodes.
Detailed Explanation
The problem is about reversing a singly linked list. We will solve this by creating a new head for the reversed list, traversing the original list, and updating the pointers as we go. The steps are:
- Initialize three pointers:
prev,current, andnext. Setprevto null (since there is no previous node initially), setcurrentto the head of the linked list, and setnextto null. - Traverse the linked list until we reach the end. For each node:
- Update
nextto be the next node in the original list. - Update
current.nextto point toprev. This effectively reverses the link between the current node and the next one. - Move
prevandcurrentone step forward. At the end of the loop,prevwill be pointing to the new head of the reversed list.
- Update
- Set the head of the reversed list to
prev.
Time complexity: O(n), where n is the number of nodes in the linked list.
Space complexity: O(1) as we are not using any additional space that scales with the input size.
Optimized Solutions
Java
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class Solution {
public static Node reverseList(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}