Published on: 06/16/2024

---

Approach 1: Iterative

Intution

Assume that we have linked list 1 -> 2 -> 3 -> .0, we would like to change it to .0 <- 1 <- 2 <- 3.

While traversing the list, we can change the current node’s next pointer to point to its previous element. Since a node dowa not have reference to its previous node, we must store its previous element beforehand. We also need another pointer to store the next node before chaning the reference. Do not forget to return the new head reference at the end!

Implementation

class Solution {
    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

Complexity Analysis

* Time Complexity: O(n) — Assume that n is the list’s length, the time complexity is O(n).

* Space Complexity: O(1)

---

---