Solution: Reverse a LinkedList

On This Page

Problem Statement

Why this is an In-place Reversal of a Linked List problem

Solution

Code

Time Complexity

Space Complexity

Problem Statement

Given the head of a Singly LinkedList, reverse the LinkedList. Write a function to return the new head of the reversed LinkedList.

Why this is an In-place Reversal of a Linked List problem

What the question says	The signal it matches
"Given the head of a Singly LinkedList, reverse the LinkedList"	the input is a linked list and the wording says reverse
"return the new head of the reversed LinkedList"	the links themselves change, not a copy of the values
reading the values out and rebuilding the list backwards	your first idea is to copy the values into an array

Flipping every link in one pass is the reverse everything variant.

The closest alternative. Copy the values into an array, reverse it, and write them back. That is correct and easier to write. It costs O(N) memory.

This chapter is about doing it with three pointers and no extra memory. Expect that to be asked for even when the question does not say so.

Constraints:

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

Solution

To reverse a LinkedList, we need to reverse one node at a time. We will start with a variable current which will initially point to the head of the LinkedList and a variable previous which will point to the previous node that we have processed; initially previous will point to null.

In a stepwise manner, we will reverse the current node by pointing it to the previous before moving on to the next node. Also, we will update the previous to always point to the previous node that we have processed. Here is the visual representation of our algorithm:

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

The time complexity of our algorithm will be O(N) where ‘N’ is the total number of nodes in the LinkedList.

Space Complexity

We only used constant space, therefore, the space complexity of our algorithm is O(1).

Mark as Completed

Thomas MinhTu Hoang

· a year ago

// public class ListNode {
//     public int Val = 0;
//     public ListNode Next;

//     public ListNode(int value) {
//         this.Val = value;
//     }
// }

public class Solution {

    public ListNode reverse(ListNode head) {
      if (head?.Next == null) return head;

      ListNode fwd = head;
      ListNode bwd = null;

      while (fwd != null) {
        bwd = new ListNode(fwd.Val) { Next = bwd };
        fwd = fwd.Next;
      }

      return bwd;
    }

Show 1 reply

Manuel

· 2 years ago



class Solution {

    public ListNode reverse(ListNode head) {
     return performReverse(null, head);
  }

  private ListNode performReverse(ListNode previous, ListNode current ){
	  if (current==null) {
	    return previous;
	  }
	    ListNode next = current.next;
	    current.next = previous;
	    return performReverse( current,next);
   }
}

Mohammed Dh Abbas

· 2 years ago


#class Node:
#  def __init__(self, value, next=None):
#    self.val = value
#    self.next = next

class Solution:
  def reverse(self, head):

    node = head
    prev = None
    
    while node.next:
      next_node = node.next
      node.next = prev
      prev = node
      node = next_node
    
    node.next = prev
    return node

catybastareaud

· 2 years ago

Show 1 reply

Luis Roel

· 3 years ago

class Solution:
  def reverse(self, head):
    prev = None
    curr = head

    while curr:
      temp = curr.next
      curr.next = prev
      prev = curr
      curr = temp
    
    return prev

Reading Progress

On This Page

Problem Statement

Why this is an In-place Reversal of a Linked List problem

Solution

Code

Time Complexity

Space Complexity