# 链表 ## LinkedList #### 查找节点操作 ~~~ function find ( item ) { var currNode = this.head; while ( currNode.element != item ){ currNode = currNode.next; } return currNode; } ~~~ #### 插入节点操作 > 将新节点的 next 属性设置为后面节点的 next 属性对应的值，然后设置后面节点的 next 属性指向新的节点 > ~~~ function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; currNode.next = newNode; } ~~~ #### 删除节点操作 首先需要两步，查找待删除节点的前一个节点，找到后将前一个节点的next指向待删除节点的next指向。 首先，查找待删除的前一个节点。 ~~~ function findPrev( item ) { var currNode = this.head; while ( !( currNode.next == null) && ( currNode.next.element != item )){ currNode = currNode.next; } return currNode; } ~~~ 接下来删除节点。 ~~~ function remove ( item ) { var prevNode = this.findPrev( item ); if( !( prevNode.next == null ) ){ prevNode.next = prevNode.next.next; } } ~~~ ## 双向列表 相比于单向列表，双向列表增加previous属性。 #### 双向列表插入节点 ~~~ function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; newNode.previous = currNode; currNode.next = newNode; } ~~~ #### 双向列表删除节点 ~~~ function remove ( item ) { var currNode = this.find ( item ); if( !( currNode.next == null ) ){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; } } ~~~ ## 循环链表 > 循环链表和单链表相似，节点类型都是一样，唯一的区别是，在创建循环链表的时候，让其头节点的 next 属性执行它本身，即 `head.next = head;` ## 相关题 #### 链表的第k个节点 ~~~ function FindKthToTail(head, k) { // write code here if (head == null || k <= 0) return null; var prev = head; var tail = head; for (var index = 0; index < k - 1; index++) { //截取长度为k的一段，prev到tail长度为k if (tail.next != null) { tail = tail.next; } else { return null; } } while (tail.next != null) { //向后移动，直到tail指向链表最后一个 prev就是倒数k个 prev = prev.next; tail = tail.next; } return prev; } ~~~ #### 逆转链表 ~~~ function ReverseList(pHead) { //a->b->c->null // write code here let current = null; let second = null; if (pHead === null || pHead.next === null) { return pHead } while (pHead !== null) { second = pHead.next; //second = a.next = b; second = b.next = c; pHead.next = current; //a.next = null; b.next = a; current = pHead; // current = a; current = b; pHead = second; //pHead = b; pHead = c; } return current; } ~~~