Reverse Linked List

---

Reverse Linked List: Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

---

Example 2:

Input: head = [1,2]
Output: [2,1]

---

Example 3:

Input: head = []
Output: []

---

Constraints:

• The number of the nodes in the list is in the range [0, 5000].
• -5000 <= Node.val <= 5000

---

Try this Problem on your own or check similar problems:

1. Palindrome Linked List
2. Reverse Linked List II
3. Remove Nodes From Linked List

Solution:

Java

public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) return head;

    ListNode prev = null, next = head, curr = prev;

    while(next != null){
        curr = next;
        next = next.next;
        curr.next = prev;
        prev = curr;
    }

    return prev;
}

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (head === null || head.next === null) return head;

  let prev = null;
  let next = head;
  let curr = prev;

  while (next !== null) {
    curr = next;
    next = next.next;
    curr.next = prev;
    prev = curr;
  }

  return prev;
};

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        prev = None
        next = head
        curr = prev

        while next is not None:
            curr = next
            next = next.next
            curr.next = prev
            prev = curr

        return prev

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* prev = nullptr;
        ListNode* next = head;
        ListNode* curr = prev;

        while (next != nullptr) {
            curr = next;
            next = next->next;
            curr->next = prev;
            prev = curr;
        }

        return prev;
    }
};

---

Time/Space Complexity:

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

---

Explanation:

We first check if the list is empty or only contains one element and we return the head of the list as it is. In this solution we have three pointers prev, next, curr. You can think of curr as the current node we're dealing with, prev the node before it, and next as our iterator through the list. We move next until we reach the end of the list, but before that we pick the current node. This is an in-place list reordering, in other words you can think of nodes as static not moving, the only thing changing is the direction of relation arrow between curr and prev (from ->, to <-). At the end of the iteration curr and prev will point to the last element in the original list and our new list head. Since we traverse the list only once we have linear time complexity O(n), and we don't create any additional data structure leading to constant space complexity. For the ones interested in recursive solution here is the short solution using recursion:

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        return helper(head, null);
    }
    private ListNode helper(ListNode head, ListNode newHead){
        if(head == null){
            return newHead;
        }
        ListNode next = head.next;
        head.next = newHead;
        return helper(next, head);
    }
}