刷力扣算法日常
题目：
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
比如：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
个人思路：假如链表的长度是5 赵倒数第二个，一般单链表查询，需要从前往后查询。
我们通过数学上面的“两数之差”就是我们要的 正数 第二个位置。
需要先计算 链表长度 用do while 如果do到最后一个null 就停止了。
链表长度-倒数位置 = 正数位置（ps有了正数位置我们就可以开始循环查询了。）
以上是思路。下面代码实现：
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution {//博客www.z88j.com 转载请表明来源谢谢了
/**
* @param ListNode $head
* @param Integer $k
* @return ListNode
*/
function getKthFromEnd($head, $k) {
$headCount = 0;//计算链表长度
$node = $head;
do{
$node = $node->next;
// var_dump($node->next);
$headCount ++;//计算长度
}while($node);
// var_dump($headCount);
$number = $headCount - $k;//计算位置 5-2 =3 所以说从正面数的位置是3.
$current = 0;
while($current < $number){
$head = $head->next;
$current ++;//当前位置走到哪里了
}
return $head;
}
}对于这个算法的 时间复杂度是 O(n) （//博客www.z88j.com 转载请表明来源谢谢了）
下面是运行时间
原创文章，作者：星辰，如若转载，请注明出处：http://www.z88j.com/96.html
微信扫一扫 