Back to Linked List
Easy
Reverse Linked List
Given the `head` of a singly linked list, reverse the list, and return the reversed list.
Examples
Input:head = [1,2,3,4,5]
Output:[5,4,3,2,1]
Input:head = [1,2]
Output:[2,1]
Constraints
The number of nodes in the list is the range [0, 5000].-5000 <= Node.val <= 5000
Approach
Maintain two pointers: `prev` (initially null) and `curr` (initially head). While `curr` is not null, save the `next` node (`curr.next`). Then reverse the pointer of `curr` to point to `prev`. Finally, move `prev` to `curr` and `curr` to `next`. When the loop finishes, `prev` will be the new head of the reversed list.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
This is the most common and optimal way to reverse a linked list in place.
Solution.java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode nextTemp = curr.next; // Save next node curr.next = prev; // Reverse pointer prev = curr; // Move prev forward curr = nextTemp; // Move curr forward } return prev; }}