Solution: Reverse a Linked List

You’re given a linked list. Write a function to reverse it.

Image for post
Image for post

Example:

Don’t create new nodes. Instead, reuse the original linked list, and modify the arrow directions in-place.

Input:
The linked list’s node values, separated by commas.

Output:
The reversed linked list’s node values, separated by commas.

Solution: Reverse a Linked List

Observe

A linked list can be split into the head node and the tail, which is also a linked list but headed by the second node.

Insights:
Treat the tail as a linked list, and reverse it by recursively calling the reverse function.

Then, the first node is appended to the reversed tail to construct the entire reversed linked list.

Algorithm

  1. Cover the edge cases of the null and single-element linked list.
  2. Get the second node from the original linked list, and recursively reverse the tail.
  3. Append the first node to the end of the reversed tail.

Code

Complexity Analysis

Let N be the length of the linked list.
We visit each node in the linked list once, so the overall complexity is O(N).

Written by

Software Engineer @Vedantu, Former Intern @Hackerrank, GSoC @Wikimedia, Former Intern @Vedantu, Codeforces(Expert)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store