AlgoDaily - Reverse a Linked List

Reverse a Linked List (Medium)

Good afternoon! Here's our prompt for today.

You may see this problem at Oracle, Ebay, Splunk, Yelp, Visa, Sap, Uipath, Jfrog, Lucid Software, Cockroach Labs, C3 Ai, and Bosch Global.

You're sent a linked list of numbers, but it's been received in the opposite order to what you need. This has happened multiple times now, so you decide to write an algorithm to reverse the lists as they come in. The list you've received is as follows:

SNIPPET

17 -> 2 -> 21 -> 6 -> 42 -> 10

Write an algorithm for a method reverseList that takes in a head node as a parameter, and reverses the linked list. It should be capable of reversing a list of any length.

You may use the example linked list for testing purposes. Your method will be called as such:

1class LinkedListNode {
2  constructor(val, next = null) {
3    this.val = val;
4    this.next = next;
5  }
6}
7
8l1 = new LinkedListNode(1);
9l1.next = new LinkedListNode(2);
10reverseList(l1);

Constraints

Length of the given LinkedList <= 100000
The nodes will always contain integer values between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

xxxxxxxxxx
​
 
var assert = require('assert');
​
function reverseList(head) {
  // Fill in this method
  return head;
}
​
function Node(val) {
  this.val = val;
  this.next = null;
}
​
function LinkedListNode(val) {
  this.val = val;
  this.next = null;
}
​
var list1 = new LinkedListNode(3);
var nodes1 = [4, 5, 6, 7, 8, 9, 10];
createNodes(list1, nodes1);
​
var list2 = new LinkedListNode(1);
var nodes2 = [2, 3, 4, 5, 6, 7, 8];
createNodes(list2, nodes2);
​
function createNodes(head, nodes) {
  for (let i = 0; i < nodes.length; i++) {

OUTPUT

Results will appear here.