菜单

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

2019年1月21日 - Php

输入一个链表,输出该链表中尾数第k个结点。第二个指针走(k-1)步,到达第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
  }
}
  1. 先求出链表中一共有稍许个节点
  2. 下一场在找到倒数第k个节点的岗位,并将其回到

 

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        ListNode current = head;
        int length = 0;
        while(current != null){
            length += 1;
            current = current.next;
        }
        ListNode tmp = head;
        int a = 0;
        if(k<= length){
            while(a != length - k ){
                    a++;
                    tmp = tmp.next;
            }
            return tmp;
        }
        else{
            return null;
        }
    }
}

相关文章

发表评论

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

网站地图xml地图