又看到一个算法
题目:链表中倒数第k个结点这个题目看到 又是一个链表 在编辑器上调试了两种方法来看一下- 思路 将链表从头到尾遍历一遍 没遍历到一个节点为计数器加1 第一遍循环完 知道了节点个数 然后再遍历一遍找到倒数第k个节点
function Node (value) { //构造函数 Node this.value = value this.next = null } Node.prototype.setNext= function(node) { this.next = node return node } var head = new Node(1) console.log(head) //Node {value: 1, next: null} 创建了1节点 接下了创建2 3 4 var two = new Node(2) var three = new Node(3) var four = new Node(4) head.setNext(two).setNext(three).setNext(four) console.log("节点"head) //Node {value: 1, next: {。。。。}} 这里创建了一个单链表 1234 console.log(FindNode(head, 2)) //这里找到倒数第2个k节点 function FindNode(head, k){ if (head == null || k <= 0) { return null } //按照思路说的来循环下 算出节点数 var nodenum = 0 var cursor = head while(nodenum !=null){ nodenum++ cursor = cursor.next } //上面这一循环 找出节点数 nodenum 4个节点 // 这里找倒数第k个 就是正数第 nodenum-k+1个节点 var index = 1 //用来从第一个开始 跟nodenum-k+1 对比 var cursor2 = head while(index !=nodenum-k+1) { //这个循环来 从第一个 1到nodenum-k+1 来循环 找到就出来 后面就是节点就是倒数k个节点 index++ cursor2 = sursor2.next } return cursor2 }复制代码 上面要循环两遍才能找到 节点 不是特别高效
看到网上一个好的解法 下面调试下
- 思路 因为单向链表不能回退 所以就定义两个指针 (1) 第一个指针从表头开始走k-1 第二个指针不动 (2) 从第k步开始 第二个指针也开始从链表头开始遍历
function Node (value) { //构造函数 Node this.value = value this.next = null } Node.prototype.setNext= function(node) { this.next = node return node } var head = new Node(1) console.log(head) //Node {value: 1, next: null} 创建了1节点 接下了创建2 3 4 var two = new Node(2) var three = new Node(3) var four = new Node(4) head.setNext(two).setNext(three).setNext(four) console.log("节点"head) //Node {value: 1, next: {。。。。}} 这里创建了一个单链表 1234 console.log(FindNode(head, 2)) //这里找到倒数第2个k节点 function FindNode(head, 2) { if (k < 0 || !head) { return null } var cursor = head //第一个指针 var cursor2 = head //第二个指针 for (var i=0; i 上面这种要比第一种效率 高点 因为只循环了一遍
两种方法 本地已经调通 有好的方法可以补充