Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Solution: Reverse a LinkedList

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.

.....

.....

.....

Like the course? Get enrolled and start learning!
Luis Roel

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
C

catybastareaud

· 2 years ago

The explanations for all the algorithm are poor

Show 1 reply
Mohammed Dh Abbas

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

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

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