Solution: Reverse a LinkedList

On This Page

Problem Statement

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.

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

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

catybastareaud

· 2 years ago

Show 1 reply

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

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);
   }
}

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

On This Page

Problem Statement

Solution

Code

Time Complexity

Space Complexity