单向链表

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

// 数组转链表
function singlyLinkedList(array) {
  this.head = null;
  let i = 0;
  let temp = null;
  while (i < array.length) {
    const node = new newNode(array[i]);
    if (i === 0) {
      this.head = node;
      temp = node;
    } else {
      temp.next = node;
      temp = temp.next;
    }
    i++;
  }
  return this;
}

// 链表翻转
function reverseLinkedList(singleTrack) {
  const newArr = [singleTrack.head.val];
  let temp = singleTrack.head;
  while (temp.next) {
    newArr.push(temp.next.val);
    temp = temp.next;
  }
  return new singlyLinkedList(newArr.reverse());
}

let singleTrack = new singlyLinkedList([1, 2, 3, 4]);
console.log(singleTrack);
console.log(reverseLinkedList(singleTrack));

// 链表第k个元素
function findIndex(singleTrack, k) {
  if (k === 1) {
    return singleTrack.head.val;
  } else {
    return eval(
      `singleTrack.head${new Array(k - 1).fill('?.next').join('')}?.val`
    );
  }
}

// 链表长度
function getTrackLength(singleTrack) {
  let temp = null,
    length = 0;
  if (singleTrack?.head?.val) {
    length = 1;
    temp = singleTrack.head;
  }
  while (temp?.next?.val) {
    temp = temp.next;
    length++;
  }
  return length;
}

// console.log(findIndex(singleTrack, 3));//第k个元素
// console.log(getTrackLength(singleTrack));//链表长度
console.log(findIndex(singleTrack, getTrackLength(singleTrack) + 1 - 5)); //倒数第k个元素

// 双指针：链表倒数第k个元素
function getLinkedListByLastIndex(linkedList, k) {
  let first = linkedList.head,
    second = linkedList.head;
  for (let i = 1; i <= k; i++) {
    first = first.next;
  }
  while (first) {
    first = first.next;
    second = second.next;
  }
  return second;
}
console.log(getLinkedListByLastIndex(singleTrack, 2)); 

// 链表翻转
var reverseLinkedList = function (head) {
  var prev = null,
    curr = head;
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};

console.log(reverseLinkedList(singleTrack.head));