链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

思路

  单向链表只有从前往后的指针而没有从后往前的指针。假设有n个节点，倒数第k个节点就是从头结点开始的第n-k+1个节点，得到节点个数n，再从头结点开始往后走n-k+1步。如果不用双指针的话，需要遍历两次链表，一次统计出节点个数，一次找倒数第k个节点。   用双指针。第一个指针走到k个位置时，第二个指针从头开始出发，两者的距离就可以始终保持为k。第一个指针走到最后时，第二个指针的位置就是倒数第k个结点的位置。要注意循环的条件，因为第一步就进行了next操作，所以应该是–k。

代码

const FindKthToTail = (head, k) => { if(!head || k<= 0) return null; let first = head; let second = head; while(--k){ if(first.next != null) first = first.next; else return null; } while(first.next != null){ first = first.next; second = second.next; } return second; }; //也可以用简单的方法，不过不是这道题想考的意思 /*function ListNode(x){ this.val = x; this.next = null; }*/ function FindKthToTail(head, k) { // write code here var result = []; while(head) { result.unshift(head); head = head.next } return result[k-1]; }

拓展

求链表中间节点：总数为奇数，返回中间节点；总数为偶数，返回中间两个节点的任意一个。 解：双指针，从头出发，一个指针一次走一步，另一个一次走两步，走的快的到达终点时走得慢的刚好到中间。

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { var tail = mid = head; // 尾部和中间结点指针 var count = 0; while (tail.next !== null) { tail = tail.next; count ++; if (count === 2) { mid = mid.next; count = 0; } } if (count === 1) { mid = mid.next; } return mid; }; //只遍历一遍，使用两个指针 tail 和 mid，tail 指向尾部，tail每走两步，mid走一步；结束之后，若 tail 最后走的是一步，说明tail 走了 (2n +1)步，总共是偶数个节点，此时 mid 还要走一步

判断单向链表是否形成环形结构。 解：双指针，从头出发，一个指针一次走一步，另一个一次走两步，如果走的快的追上了走的慢的，那么就是环形链表；如果走到了末尾（next为空）还没追上，就不是环形。 https://blog.csdn.net/a_studycx/article/details/53999343