Iterative Approach: This approach involves using a loop to traverse the linked list and reverse the direction of the next pointers at each step. Start with three pointers: prev as null, curr as the head of the list, and nxt to temporarily store the next node. In each iteration, change the curr.next to prev, move prev to curr, and curr to nxt. The loop ends when curr becomes null, with prev being the new head.
Time Complexity: O(n), where n is the number of nodes in the linked list because each node is processed once.
Space Complexity: O(1) as it uses only a constant amount of space.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode ReverseList(ListNode head) {
12 ListNode prev = null;
13 ListNode curr = head;
14 while (curr != null) {
15 ListNode nxt = curr.next;
16 curr.next = prev;
17 prev = curr;
18 curr = nxt;
19 }
20 return prev;
21 }
22}The C# solution also utilizes the three-pointer technique: prev, curr, and nxt. Similar to other languages, these pointers manage the reversal process of the linked list iteratively.
Recursive Approach: In this method, you move to the end of the list via recursive calls while reversing the next pointers on the way back. The base case for the recursion is when the list is empty or when it contains only one node. In each call, move to the next node, reverse the rest of the list, use the next pointer's next field to point to the current node, and finally return the head of the reversed list.
Time Complexity: O(n), due to n recursive calls.
Space Complexity: O(n), for stack space in recursion.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode() {}
5 ListNode(int val) { this.val = val; }
6 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7}
8
9public class Solution {
10 public ListNode reverseList(ListNode head) {
11 if (head == null || head.next == null) return head;
12 ListNode p = reverseList(head.next);
13 head.next.next = head;
14 head.next = null;
15 return p;
16 }
17}In Java, the recursive function continues traversing until it reaches the list's last node, then starts reversing pointers until reaching the original head. Each recursive call returns the new head of the reversed sublist.