Last week I posted my second contest with a coding problem to solve.
Now it's time to acknowledge and reward the winners!

Contest #2

In a Linked list, each node has a value and a next node.
Given a Linked list:

Write a function that reverse the linked list, using a recursive algorithm.
Write a function that reverse the linked list, using a iterative algorithm.
- For instance: given A -> B -> C it returns C -> B ->A

You don't have to clone the nodes, you must just work on their next properties.

The preferred language to use this time is javascript, but you can also use other languages as well. You will need to translate the starting code to the language of your choice.

Winners

There were 5 participants and all of them solved the problems well!
Perhaps the problem was easier than I thought! I’ll try and make the next ones harder!

As promised, the rewards will be based on clarity of the code and the time of submission.

Hope to see your solutions to my future contests too!

Best solution

function reverseRecursive(obj) {
  var next = obj && obj.next;
  if(!next){
    return obj;
  }
  var reversedTail = reverseRecursive(next);
  obj.next = null;
  next.next = obj;
  return reversedTail;
}

function reverseIterative(obj) {
  var reversed;
  while(obj){
    var next = obj.next;
    obj.next = reversed;
    reversed = obj;
    obj = next;
  }
  return reversed;
}


/***************************/
/***************************/
/* DO NOT CHANGE DOWN HERE */
/***************************/
/***************************/


function Obj(v, next) {
  this.v = v;
  this.next = next;
}
Obj.prototype.toString = function() {
  var next = this.next ? ' -> ' + this.next.toString() : '';
  return this.v + next;
};
Obj.prototype.clone = function() {
  return new Obj(this.v, this.next && this.next.clone());
};

function arrayToObj(array) {
  var obj;
  for (var i = array.length - 1; i >= 0; i--) {
    obj = new Obj(array[i], obj);
  }  
  return obj;
}



function test(array) {
  var obj = arrayToObj(array);
  console.log('Original:')
  console.log(obj && obj.toString());

  var r1 = reverseRecursive(obj && obj.clone());
  console.log('Reversed (recursive algorithm):');
  console.log(r1 && r1.toString());

  var r2 = reverseIterative(obj && obj.clone());
  console.log('Reversed (iterative algorithm):');
  console.log(r2 && r2.toString());

  console.log();
}

test([1, 2, 3, 4, 5, 6]);
test([1]);
test([]);

Rewards

The contest post total liquid reward is: 9.409 SBD

1st price: 50%
- @hendrikcrause --- 4.704 SBD
2nd price: 25%
- @codingdefined --- 2.352 SBD
3rd price: 12.5%
- @chasmic-cosm --- 1.176 SBD
4th price: 6.25%
- @pps --- 0.588 SBD
5th price: 3.125%
- @jjb777 --- 0.294 SBD

Thanks for taking part of the challenge!

Armando 🐾

Thanks @armandocat.

For anyone interested in knowing how the code works, here goes:

In order to reverse a linked list, one has to loop through the entire list and change the 'next' pointer of each node to point to the previous node.

In the case of a recursive function, we "loop" through the list by reversing the current node and the calling the recursive function again on the next node. A recursive function also always need to start with a stop condition to prevent infinite loops and stack-overflows. In this case the stop condition is when the node it's given is either null or has no next node.

In the case of an iterative function. We loop through the list with well... a loop. A while loop in this case where we check that the current node we're reversing isn't null.

That's it. Simple really... if you have the solution in front of you 😝.

Can't wait for the next one.

Coding challenge #2 - Winners!

Contest #2

Winners

Best solution

Rewards

Thanks for taking part of the challenge!