educative.io

Educative

A clearer, explained solution

https://playcode.io/899439

class Node {

  constructor(value, next = null) {

    this.value = value;

    this.next = next;

  }

  print_list() {

    result = "";

    temp = this;

    while (temp !== null) {

      result += temp.value + " ";

      temp = temp.next;

    }

    console.log(result);

  }

}

const reorder = function (head) {

  let reversedSecondHalf = reverseListInPlace(getMiddleNode(head))

  // head contains only the first original half

  // because the reversed second half's last node.next is null

  // e.g: 2,4,6,8,null / 12,10,8,null

  //            ^- same node --^

  let firstHalf = head

  while (firstHalf !== null && reversedSecondHalf !== null) {

    // store references to the original next nodes for iteration

    const next = firstHalf.next

    const revNext = reversedSecondHalf.next

    // set the next node to the head of the reversed half

    firstHalf.next = reversedSecondHalf

    // move the iteration forward

    firstHalf = next

    // prevent the last node looping into itself

    if (firstHalf !== reversedSecondHalf) {

      // set the next node to the head of the first half

      reversedSecondHalf.next = firstHalf

    }

    // move the iteration forward

    reversedSecondHalf = revNext

  }  

  // terminate the list

  if (firstHalf.next !== null) {

    firstHalf.next = null

  }

}

const reverseListInPlace = (head) => {

  let reversed = null

  while (head !== null) {

    // store ref to next

    const next = head.next

    // reverse order

    head.next = reversed

    reversed = head

    // set next iteration

    head = next

  }

  return reversed

}

const getMiddleNode = (head) => {

  let slow = head

  let fast = head

  while (fast !== null && fast.next !== null) {

    slow = slow.next

    fast = fast.next.next

  }

  return slow

}

head = new Node(2)

head.next = new Node(4)

head.next.next = new Node(6)

head.next.next.next = new Node(8)

head.next.next.next.next = new Node(10)

head.next.next.next.next.next = new Node(12)

reorder(head)

head.print_list()

Type your question above this line.

Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6429532024209408

Hi Nicolas_F,
Thank you for sharing feedback and solution with Educative.
It is highly appreciated.

1 Like