Converting array to Linked list - from Eloquent Javascript - Stack Overflow

admin管理员组

文章数量:1181440

It is one of the challenge in the book I fail to understand, or my brain is unable to break it down. Here is the solution function:

 function arrayToList(array) {
  var list = null;
  for (var i = array.length - 1; i >= 0; i--)
    list = {value: array[i], rest: list};
  return list;
}

console.log(arrayToList([10, 20]));
// → {value: 10, rest: {value: 20, rest: null}}

so we are looping the array inversly so first time list should be:

list = {value:20, rest:{value:20, rest:**mind blows here**}}

can any one help me through this process?

It is one of the challenge in the book I fail to understand, or my brain is unable to break it down. Here is the solution function:

 function arrayToList(array) {
  var list = null;
  for (var i = array.length - 1; i >= 0; i--)
    list = {value: array[i], rest: list};
  return list;
}

console.log(arrayToList([10, 20]));
// → {value: 10, rest: {value: 20, rest: null}}

so we are looping the array inversly so first time list should be:

list = {value:20, rest:{value:20, rest:**mind blows here**}}

can any one help me through this process?

• javascript
• arrays
• linked-list

Share Improve this question Follow asked Sep 3, 2015 at 11:57 Haris KhanHaris Khan 17111 gold badge22 silver badges1111 bronze badges

Add a comment  | 

8 Answers 8

Sorted by: Reset to default 20

reducer can be used to create linked list from array elements.

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

let input = [1, 2, 3];


let head = input.reverse().reduce((acc, curr) => {
  if (acc == null) {
    acc = new ListNode(curr);

  } else {
    acc = new ListNode(curr, acc);
  }
  return acc;
}, null);

console.log(head);

Here it is:

function L(val){
    this.val = val;
    this.next = null;
}

//We have to develop
/*
L{
    val:1,
    next:{
        val:2,
        next: {
            val:3,
            next: {
                val:4,
                next:null
            }
        }
    }
}
*/

function createL(a){
    let node, temp;
    for(let i=a.length-1; i >= 0; i--){
        if(!node)
            node = new L(a[i]);
        else {
            temp = new L(a[i]);
            temp.next = node;
            node = temp;
        }
    }
    return node;
}

createL([1,2,3,4]);

Just step through it, keeping track of the values of each name/variable as you go:

Initially:

array = [10, 20]
list = null
i = 1

Next step:

array = [10, 20]
list = {value: 20, rest: null}
i = 1

Next step:

array = [10, 20]
list = {value: 20, rest: null}
i = 0

Next step:

array = [10, 20]
list = {value: 10, rest: {value: 20, rest: null}}
i = 0

At this point the loop, and the function, ends.

The key is when operations are performed. Since this is imperative style programming (as opposed to (pure) functional), the value associated with a name (variable) can be changed during the execution of the code. So when list is read and when list is assigned a new value is crucial.

A simple approach will be to create a dummy node. Then, push each array element into the dummy node. Then return the dummy node's next node.

class ListNode {
    constructor(data) {
        this.data = data
        this.next = null                
    }
}

const arr = [1,2,3];

let dummy = new ListNode(-1);
let dummyHead = dummy;

for(let i = 0; i < arr.length; i++){
  dummyHead.next = new ListNode(arr[i]);
  dummyHead = dummyHead.next;
}

Basically you create an object that has inside 2 elements. first element is the value, the second element is the rest of the list. in the line list = {value:20, rest:{value:20, rest:list}} we are basically creating the list from end to start, so you always add the list former status. so let's say we had 3 elements [10,20,30]. 1. we start in 30 - creating an object called list with the elements value = 30, list = null. 2. we are in 20 - taking the list object that looks like this {value:30, rest:null} and placing it inside of a new object with the 20 value, so we have {value: 20, rest:{**old list** --> {value:30, list:null} }} now we change the reference of list to point to the newly created object. list = {value: 20, rest:{**old list** --> {value:30, list:null} }} 3. we do the same as in 2.

now you have a list. (hope I was clear)

update hasan.in answer in 2022.I like that, and it can be shorter and more direct.

function ListNode(val, next) {
  this.val = (val===undefined ? 0 : val)
  this.next = (next===undefined ? null : next)
}

const arrToList = (arr) => arr.reduceRight((last, val)=> last = last === null ? new ListNode(val) : new ListNode(val, last),null)

const arr = [1,2,3]
console.log(arrToList(arr))
// {val: 1, next: {val: 2, next: { val: 3, next:  null}}}

typescript version

class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

const arrToList = (arr:number[]) => arr.reduceRight<null|ListNode>((last, val)=> last = last === null ? new ListNode(val) : new ListNode(val, last),null)

const arr = [1,2,3]
console.log(arrToList(arr))

With some extra logs

function arrayToList(array) {
  var list = null;
  for (var i = array.length - 1; i >= 0; i--) {
    console.log(i); //2, then 1
    console.log(array[i]); //20, then 10
    list = {
      value: array[i],
      rest: list //null, then {value:20, rest: null}
    };
  }
  return list;
}
console.log(arrayToList([10, 20]));
//{ value: 10, rest: { value: 20, rest: null } }

you can see that although you are iterating through the list in reverse, the list object's value property will be the last iterated array element. The rest property will be a copy of list at that iteration.

let strings = ['a','b','c','d']
function fnConvertArray(arr) {
  let obj = {}
  while (arr.length){
    let s = arr.shift();
    let snext = arr.map(v=>v).shift();
    obj[s] = {next: snext}
  }
  return obj;
}
// {
//   a: { next: 'b' },
//   b: { next: 'c' },
//   c: { next: 'd' },
//   d: { next: undefined }
// }
console.log(fnConvertArray(strings));

本文标签： Converting array to Linked listfrom Eloquent JavascriptStack Overflow