php链表中倒数第k个节点 解法

刷力扣算法日常

题目:

输入一个链表,输出该链表中倒数第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 转载请表明来源谢谢了)

下面是运行时间

php链表中倒数第k个节点 解法

原创文章,作者:星辰,如若转载,请注明出处:https://www.z88j.com/96.html

(7)
打赏 微信扫一扫 微信扫一扫
上一篇 2020年12月2日 上午12:14
下一篇 2020年12月9日 上午12:48

相关推荐

发表回复

登录后才能评论