输入一个链表，输出该链表中倒数第k个结点(C语言)

电玩女神 2022-12-29 12:50 82阅读 0赞

题目描述  
输入一个链表，输出该链表中倒数第k个结点。  
示例1  
输入

> 1,\{1,2,3,4,5\}

返回值

> \{5\}

# 思路1：暴力查找 #

直接遍历链表，算出链表长度n，然后倒数第k个，就是输出链表正数第n-k个  
注意:以下几种情况直接返回NULL

> 链表为NULL或者k<=0  
> k值大于链表长度

# 代码 #

typedef struct ListNode Node;
    struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
    {
        
        //判断链表非空
        if(pListHead==NULL || k <=0)
        {
        
            return NULL;
        }
        
        //定义一个计数器用来技术链表长度
        int count =0;
        //遍历链表
        Node * cur = pListHead;
        while(cur)
        {
        
            cur=cur->next;    //cur指针右移
            ++count;    //计数器+1
        }
        
        //判断k是否大于链表长度
        if(count<k)
        {
        
            return NULL;
        }
        //新的头节点
        Node * NewHead = pListHead;
        for(int i=0;i<count-k;i++)
        {
        
            NewHead=NewHead->next;
        }
        
        return NewHead;
        
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

# 思路2：快慢指针 #

设定两个快慢指针，快指针比慢指针先走k步，这样当快指针走到最后一个节点时，慢指针刚好时倒数第k个节点  
![图片来自于牛客网][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]

# 代码 #

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
        
        // write code here
        //设一个快慢指针，快指针比慢指针快n步
        if(pListHead==NULL || k<=0)
        {
        
            return NULL;
        }
        Node * fast =pListHead;
        
        
        //快指针先走k步
       
        while(k--)
        {
        
            if(fast==NULL)
                return NULL;
            fast=fast->next;
        }
        
        //慢指针开始走
        Node * slow =pListHead;
        while(fast!=NULL)
        {
        
            slow=slow->next;
            fast=fast->next;
        }
        
        return slow;
        
    }

![在这里插入图片描述][20201222164031898.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221120/49507b35abe64075ad49c82daf9ae38f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: /images/20221120/09cf32196fdd4f3b9d83b3addc398709.png
[20201222164031898.png]: /images/20221120/e24747ff37544791b37d7b446cb67006.png