Data Structures

Reverse Linked List

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

Example:

First Few Test Cases:

To solve this problem, we need to "reverse" all the pointers in the list. To do this, we have to start at the head node, and reverse all the nodes one at a time:

In order to reverse a node, we have to keep track of the current node curr that we want to reverse. We also have to keep track the previous node prev, so that we can point the current node backwards to it. It turns out that we also need to save a pointer to the next node in the list temp_next so that we still have access to it when we reverse the pointer.

Here's a visual of how you reverse a single node:

Here's the code for the above image:

To reverse the whole list, we repeat the above code until we've reversed the entire list.

We start with these prev\small \tt prev and curr\small \tt curr pointers:

And we finish with these pointers:

When we finish, we should return the head of the reversed list which is the prev\small \tt prev pointer. Here's how you code this up:

Mark as Completed:
Submits:
reverseList
Imports:
ListNode
Test your code to get an output here!
reverseList(
)
Test your code to get an output here!