/**
* 公众号:「一个不甘平凡的码农」
* 2019/3/24
* @author 小鹿
* 功能:求链表的中间节点
*/
//定义结点
class Node{
constructor(data){
this.data = data;
this.next = null;
}
}
//定义链表
class LinkedList{
constructor(){
this.head = new Node('head');
}
//根据 value 查找结点
findByValue = (value) =>{
let currentNode = this.head;
while(currentNode !== null && currentNode.data !== value){
currentNode = currentNode.next;
}
//判断该结点是否找到
console.log(currentNode)
return currentNode === null ? -1 : currentNode;
}
//根据 index 查找结点
findByIndex = (index) =>{
let pos = 0;
let currentNode = this.head;
while(currentNode !== null && pos !== index){
currentNode = currentNode.next;
pos++;
}
//判断是否找到该索引
console.log(currentNode)
return currentNode === null ? -1 : currentNode;
}
//插入元素(指定元素向后插入)
insert = (value,element) =>{
//先查找该元素
let currentNode = this.findByValue(element);
//如果没有找到
if(currentNode == -1){
console.log("未找到插入位置!")
return;
}
let newNode = new Node(value);
newNode.next = currentNode.next;
currentNode.next = newNode;
}
//根据值删除结点
delete = (value) =>{
let currentNode = this.head;
let preNode = null;
while(currentNode !== null && currentNode.data !== value){
preNode = currentNode;
currentNode = currentNode.next;
}
if(currentNode == null) return -1;
preNode.next = currentNode.next;
}
//遍历所有结点
print = () =>{
let currentNode = this.head
//如果结点不为空
while(currentNode !== null){
console.log(currentNode.data)
currentNode = currentNode.next;
}
}
//功能:求中间结点
//步骤:
// 1、声明两个指针(fast、slow)
// 2、判断 fast 的下一结点和下下结点是否为 null?
// 3、如果满足条件,fast 前移动两位, slow 前移动一位
// 返回 slow 就是中间结点
findMidNode = () =>{
let fast = this.head;
let slow = this.head;
while(fast.next !== null && fast.next.next !== null){
fast = fast.next.next;
slow = slow.next;
}
console.log(slow)
return slow;
}
}
// 测试
const list = new LinkedList();
list.insert('1','head');
list.insert('2','1');
list.insert('3','2');
list.insert('4','3');
list.insert('5','4');
list.insert('6','5');
list.print();
console.log('--------------------求链表的中间结点---------------------')
console.log(list.findMidNode().data)