链表中倒数第k个节点

ryluo 2020-06-27 10:55:53

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

注意:

样例

输入:链表:1->2->3->4->5 ,k=2

输出:4

分析:

  1. 使用快慢指针,快慢指针都初始化为头节点,然后快指针先走k步,然后快慢指针一起走,直到快指针指向NULL。但是使用快慢指针需要注意,有可能k大于链表长度,所以快指针在走的时候需要注意是否已经到了节点末尾,如果到了需要提前停止,然后返回空。
  2. 先使用一个指针将链表遍历一遍,计算链表的长度n,然后在定义一个指针直接走n-k+1,就是导数第k个元素,这种方法可以提前将k大于链表长度的情况给判掉。

两种方法的算法复杂度都为O(2n-k)=O(n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        auto fast = head, slow = head;
        int i = k;
        for(i; i > 0 && fast; i--) fast = fast->next;
        if (i > 0) return nullptr;

        while(fast)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

在下面这种情况,数组的下标和长度很容易出现问题,需要仔细思考。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* head, int k) {
        auto p = head;
        int n = 0;
        while(p)
        {
            n++;
            p = p->next;
        }
        if(k > n) return NULL;

        auto res = head;
        for(int i = 0; i <= n - k - 1; i++) res = res->next;
        return res;
    }
};