菜单

[华为]输出单向链表中倒数第k单结点

2018年11月16日 - Php

输入一个链表,输出该链表中倒数第k个结点。第一单指针动(k-1)步,到达第k只节点,两只指针同时于后活动,当第一个结点到达最终的上,第二单结点所在位置就是倒数第k单节点了

输入一个只为链表,输出该链表中倒数第k个结点,链表的倒数第1单结点为链表的尾指针。

<?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
  }
}

链表结点定义如下:

 

struct ListNode

{

      int       m_nKey;

      ListNode* m_pNext;

};

详细描述:

接口说明

原型:

ListNode* FindKthToTail(ListNode* pListHead, unsignedint k);

输入参数:

        ListNode* pListHead  单向链表

     unsigned int k  倒数第k个结点

输出参数(指针指向的内存区域管中):

    无

返回值:

        正常返回倒数第k个结点指针,异常返回空指针

输入描述:

输入说明
1 输入链表结点个数
2 输入链表的价值
3 输入k的值

输出描述:

出口一个平头

输入例子:
8
1 2 3 4 5 6 7 8
4
输出例子:
5

//利用两个指针遍历找到链表的倒数第K个元素

#include<iostream>

using namespace std;

struct ListNode 
{    
    int val;    
    ListNode* next;    
    ListNode(int a) 
    {        
        val=a;        
        next=NULL;   
    }
};


ListNode *findKth(ListNode *head,int k) 
{    
    if(k<1)        return NULL;    
    ListNode *p1 = head;    
    ListNode *p2 = head;    
    for(int i = 0; i<k-1; i++) 
    {        
        p1 = p1->next;    
    }    

    while(p1 !=NULL) 
    {        
        p1 = p1->next;       
        p2 = p2->next;   
    }    
    return p2;
}


int main() 
{    
    int n;    
    while(cin>>n) 
    {        
        int val;       
        ListNode *head = new ListNode(0);        
        ListNode *p = head;        

        for(int i = 0; i<n; i++)       
        {            
            cin>>val;            
            ListNode *q = new ListNode(val);            
            p->next = q;            
            p = p->next;       
        }        

        int k;        
        cin>>k;        

        ListNode *temp = findKth(head,k+1);//本题的特殊之处,存在倒数第0个        
        cout<<temp->val<<endl;    
    }    
    return 0;
}

  

相关文章

发表评论

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

网站地图xml地图