链表中倒数第k个节点 - 代码的鲁棒性(双指针法)

我会带着你远行 2022-12-19 08:54 88阅读 0赞

## 链表中倒数第k个节点 ##

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

**示例：**

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

## 分析 ##

这个题没什么难度，但是可以用好多种方法求解

*  栈
 *  快慢双指针
 *  递归

> 对于指针的话，可能还是为了考察指针的一些基本操作，以及程序的健壮性。

## 解法 ##

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    
    struct ListNode* getKthFromEnd(struct ListNode* head, int k){ 
        // 代码的鲁棒性
        if(head == NULL || k <= 0)
            return NULL;
        //定义两个指针
        struct ListNode * p = head, * node = head; 
        // k--
        // p在0位置，node在k位置
        while(k--){ 
            //如果当前节点不为空
            if(node != NULL){ 
                node = node->next;
            }else{ 
                return NULL;
            }
        }
        //当node不为空时，向后移动，当node为空时，说明此时在尾节点后面的一个节点
        while(node != NULL){ 
            // p在0，node在k
            //p移动一下，p在1，当node再移动时如果时空，则不会再进入
            p = p->next;
            node = node->next;
        }
        return p;
    }