Question

Javascript Problem: List Reverse

Given a list:

var list = {
  value: 1,
  next: {
    value: 2,
    next: {
      value: 3,
      next: null     
    }
  }
};

Reverse the order of the list so that it looks like:

var list = {
  value: 3,
  next: {
    value: 2,
    next: {
      value: 1,
      next: null
    }
  }
};

Use the following shell if needed:

//assignment1.js

function reverseList(list) {
    // your code here
    ...
    return reversedList;
}

Example Test Case(s):

Arguments: { value: 1, next: { value: 2, next: { value: 3, next: null } } };
Returns: { value: 3, next: { value: 2, next: { value: 1, next: null } } };

Arguments: { value: "a", next: { value: "b", next: { value: "c", next: null } } };
Returns: { value: "c", next: { value: "b", next: { value: "a", next: null } } };

Requirements:

• You cannot use the built-in reverse() function.
• null is non-existent object, you may use an empty object instead if desired.
• Your function should be able to reverse a list of values of any type.
• You must use at least one array to solve the problem.

Answer 1

// Javascript program to reverse the order of the list

// function to reverse the order of the input list and return the reversed list
function reverseList(list) {
  
   // create an empty reversedList
   reversedList = {};
  
   // create an empty array to store the elements of the list
   data = [];
  
   // set curr to list i.e start of the list
    curr = list;
  
   // loop that continues till the end of the list i.e until null or empty object is not encountered
   while((curr != null) && (Object.keys(curr).length != 0))
   {
       data.push(curr.value); // insert curr's value at the end of data
       curr = curr.next; // move curr to next node
   }
  
   // set curr to reversedList start pointer
   curr = reversedList;
  
   // loop over the data array in reverse order i.e from last to first
   for(var i=data.length-1;i>=0;i--)
   {
       // reversedList is an empty object
       if(Object.keys(reversedList).length == 0){
           // set reversedList list value to ith element of data and next to null
           reversedList =    {value:data[i], next: null};
           curr = reversedList; // set curr to reversedList
       }  
       else // reversedList is not an empty object
       {  
           // set value and next for node next to curr
           curr.next = {value:data[i], next:null};
           curr = curr.next; // move curr to next node
       }  
   }
  
return reversedList;
}

// test the function
var list = {
value: 1,
next: {
value: 2,
next: {
value: 3,
next: null
}
}
};

console.log(reverseList(list));

var list = { value: "a", next: { value: "b", next: { value: "c", next: null } } };
console.log(reverseList(list));

//end of program

Output: