Reverse Linked List

EasyLinked Listreverse-linked-list

Given the head of a singly linked list, reverse the list, and return the new head.

Constraints:

  • The number of nodes in the list is in the range [0, 1000].
  • Node values are in the range [-1000, 1000].

Example 1:

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

Example 2:

Input: head = [] Output: []

Recommended time and space complexity

You should aim for a solution with O(n) time complexity and O(1) space complexity for the iterative approach or O(n) for the recursive approach, where n is the length of the list.


Hint 1

A brute force approach would be to create a new list and copy elements in reverse order. This would be an O(n) time and O(n) space solution. Can you think of a more efficient approach?


Hint 2

Can you reverse the list by changing the links between nodes without using additional memory?


Hint 3

Use three pointers: `prev`, `curr`, and `next`. Move them through the list, changing the direction of the links.

This problem tests the ability to efficiently reverse a singly linked list. It helps develop skills in working with pointers and recursion, as well as improves understanding of time and space complexity of algorithms. Solving this problem promotes logical thinking and the ability to optimize code for working with large amounts of data.
solution.js · saved

Input

[1, 2, 3, 4, 5]

Expected Output

[5, 4, 3, 2, 1]