前端算法学习js链表定义及翻转

1.定义节点类

function Node(element) {
  this.element = element;
  this.next = null;
}

2.定义链表及增删查改方法

function linkList() {
  this.head = new Node('head');
  //调用对链表增删删改的方法
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.findByIndex = findByIndex;
  this.reserveList = reserveList;
}
function find(item) {
  var curNode = this.head;
  while (curNode.element != item) {
    curNode = curNode.next;
  }
  return curNode;
}
//通过索引找元素
function findByIndex(index) {
  var curNode = this.head;
  let i = 0;
  while (i != index) {
    i++;
    curNode = curNode.next;
  }
  return curNode;
}
function insert(newElement, item) {
  var newNode = new Node(newElement);
  var current = this.find(item);
  newNode.next = current.next;
  current.next = newNode;
}
//打印链表的方法
function display() {
  var currNode = this.head;
  while (!(currNode.next == null)) {
    currNode = currNode.next;
    console.log(currNode);
  }
}

另外写了一个输入数组转为链表存储的方法
//传进数组存在链表

function toList(array) {
  var list = new linkList();
  // console.log(list);
  list.insert(array[0], 'head');
  for (let i = 1; i < array.length; i++) {
    list.insert(array[i], array[i - 1]);
  }
  // list.display();
  return list;
}

3.算法：链表反转的方法
关于书写链表的一些方法时，容易出错的难点在于循环时next指针指向经常容易弄错，有时候已经改变了next指针的指向，对于指向问题最好多画图。

//关于链表翻转的方法,比如，链表为1→2→3→4→5→6，k=2，则翻转后2→1→6→5→4→3
function reserveList(k) {
  let midItem = this.findByIndex(k);
  let midItem2 = this.findByIndex(k + 1);

  //中间这部分代码实现了整个链表的翻转
  let prevNode = this.head.next;
  let currentNode = prevNode.next;
  let item;
  while (currentNode != null) {
    item = currentNode.next;
    currentNode.next = prevNode;
    prevNode = currentNode;
    currentNode = item;
  }
  item = this.head.next;
  this.head.next = prevNode;
  item.next = null;

  let newMid = item;
  //因为不是整个链表翻转，前后两部分分别翻转，所以在做一些调整
  let newMid2 = this.head.next;
  this.head.next = midItem;
  newMid.next = newMid2;
  midItem2.next = null;
  this.display();
}


var x = toList([1, 2, 3, 4, 5, 6, 7, 8]);
var y = x.findByIndex(3);
var z = x.reserveList(4);
测试例子