[PHP] 数据结构-输出链表倒数第k个结点PHP达成

输入一个链表,输出该链表中尾数第k个结点。第四个指针走(k-1)步,到达第k个节点,三个指针同时将来移动,当第二个结点到达最终的时候,首个结点所在地点就是尾数第k个节点了


举例

FindKthToTail(node, -2);

365bet亚洲真人 1
FindKthToTail(empty , 2);

365bet亚洲真人 2
FindKthToTail(node, 100);

365bet亚洲真人 3

FindKthToTail(node, 2);

365bet亚洲真人 4

题目:
输入一个链表,输出该链表中尾数第k个结点。

 

  • [2论断一个单链表中环的进口节点]
    第一利用1中方法判断链表中是或不是有环,获取环中任意一个节点,然后拿走环的长短为n。
    下一场定义五个指针,一个指针先走n步,然后八个指针在以同样的快慢移动,当第一个指针走到进口节点时,第二个指针刚好走了一圈,也抵达入口节点,那时就找到了环的进口节点。

题材叙述

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


解法
分析:
好端端解法:首先遍历四遍得到链表节点个数n,然后早先走n-k步即到达倒数第k个节点
日子复杂度O(n+n-k)
遍历五次的做法:
设三个指针同时针对表头,第二个指针先走k步,此时三个指针的距离为k,那么八个指针同时将来走,当首个指针到达链表结尾时,另一个指南针即指向了尾数第k个结点

<?php
class Node{
        public $data;
        public $next;
}
//创建一个链表
$linkList=new Node();
$linkList->next=null;
$temp=$linkList;
for($i=1;$i<=10;$i++){
        $node=new Node();
        $node->data="aaa{$i}";
        $node->next=null;
        $temp->next=$node;
        $temp=$node;
}
//输入一个链表,输出该链表中倒数第k个结点。

function find($linkList,$k){
        //速度快的指针
        $fast=$linkList;
        //速度慢的指针
        $slow=$linkList;
        //快指针先移动k-1步
        for($i=0;$i<$k-1;$i++){
                $fast=$fast->next;
        }   
        if($fast->next==null){
                return false;
        }   
        //快慢指针一块移动
        while($fast->next!=null){
                $fast=$fast->next;
                $slow=$slow->next;
        }   
        return $slow;
}


$knode=find($linkList,2);
var_dump($knode);

object(Node)#10 (2) {
  ["data"]=>
  string(4) "aaa9"
  ["next"]=>
  object(Node)#11 (2) {
    ["data"]=>
    string(5) "aaa10"
    ["next"]=>
    NULL
  }
}

链表中尾数第k个结点

  • 3在链表的第k个职责插入一个结点
    若链表为空,则一贯将插入数据作为首个结点;
    若插入首个职位和插入最后一个地点,都要考虑到。

心想事成代码

// Node用来标识结点,element用来保存节点上的数据,next用来保存指向下一个节点的链接
function Node(element) {
    this.element = element;
    this.next = null;
}

/* 在Node的原型链上添加insert方法,
判断链表是否为空,若为空,则在添加第一个结点,
若不为空,则在当前结点后面添加新的结点。*/
Node.prototype.insert = function(newElement) {
    if (this.element === undefined) {
        this.element = newElement;
    } else {
        var curNode = this;
        while (curNode.next !== null) {
            curNode = curNode.next;
        }
        var newNode = new Node(newElement);
        curNode.next = newNode;
        newNode.next = null;
    }
};

// 查找链表中倒数第k个结点
function FindKthToTail(head, k) {
    if (head.element === undefined) {
        return new Error("head为空链表!");
    }
    if (k <= 0) {
        return new Error("k小于等于0!");
    }
    var pre = head;
    var last = head;
    for (var i = 1; i < k; i++) {
        if (pre.next !== null) {
            pre = pre.next;
        } else {
            return new Error("k值过大!");
        }
    }
    while (pre.next !== null) {
        pre = pre.next;
        last = last.next;
    }
    return last;
}

var node = new Node(); 
node.insert("Kobe");
node.insert("Curry");
node.insert("Russel");
node.insert("Klay");
node.insert("Tracy");
console.log(node);
var empty = {};
public static ListNode reverseNode(ListNode node) {
        if (node == null)
            return null;
        ListNode reverseNode = null;
        ListNode head = node;
        ListNode preNode = null;
        while (head != null) {
            ListNode nextNode = head.next;
            if (nextNode == null)
                reverseNode = head;
            head.next = preNode;
            preNode = head;
            head = nextNode;
        }
        return reverseNode;
    }

思路

  1. 365bet亚洲真人,三个指针,先让第四个指针和首个指针都指向头结点,然后再让第二个指正走(k-1)步,到达第k个节点;
  2. 接下来几个指针同时以后运动,当首个结点到达最终的时候,第一个结点所在地点就是尾数第k个节点了。
  3. 主旨考察鲁棒性,由此要看清空值和负值以及k值不能够跨越链表的长短。
  4. 大旨链表不含头结点。

发表评论

电子邮件地址不会被公开。 必填项已用*标注