首页 > 代码库 > 链表中倒数第K个结点

链表中倒数第K个结点

2024-07-07 15:43:14   231人阅读

题目：输入一个链表，输出改链表倒数第K个结点。

分析：常规方法可能就是，先遍历一遍链表，找到链表长度length，那么我们只需要第二次遍历length-k+1个结点就可以找到倒数第k个结点。

        比较好的方法是采用两个指针，让一个指针先走K-1步，后面的指针再跟上。这样只需要遍历一遍。

注意：1.提高容错性，在链表为空 或者k为空。还有k大于链表长度。

        2.链表下一个结点，我们采用p=p->next.指针指向的数组我们采用p++;

typedef int Type;
struct listNode{
    Type data;
    listNode *nextNode;
};

listNode* findInverOfK(listNode * pHead,int k)
{
   
   //还有其他各种情况的考察,容错性检查
   //链表递增到下一个结点：p=p->next，如果是指针指向一个数组，则用p++;
   if(NULL==pHead||k<=0)
        return NULL;                 //注意出错就返回NULL
  
       listNode *p_first=pHead;
       listNode *p_second=pHead;
       for (int i=0;i<k-1;i++)        //注意是k-1
       {
           if(p_second->nextNode!=NULL)
               p_second=p_second->nextNode;
           else
               return NULL;
       }
       while(p_second->nextNode!=NULL)
       {
           p_first=p_first->nextNode;  //注意不是p_first++;除非指向的是一个数组
           p_second=p_second->nextNode;
       }
       return p_first;
   
}

 


联系
我们