14.链表中倒数第k个结点.md

14.链表中倒数第k个结点

题目描述

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

解题思路

• 思路一，简单思路，先遍历整个链表，获得链表的长度，然后求出倒数第k个结点的下标，然后再遍历过去。

• 思路二，设置两个指针，见下面的图，一目了然，两种方法其实复杂度差不多，实际上都是指针过两遍：

  

  设置两个指针p和p1，当p跑到第k个位置的时候，p1再和p一起跑，这样当p跑到最后一个的时候，p1指向的就是倒数第k个数。

代码

• 方法一，简单思路，两次遍历

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL) return NULL;
        int length = 1;
        ListNode* p = pListHead;
        while(p->next){
            length++;
            p = p->next;
        }
        if(length < k) return NULL;
        int idx = length - k;
        p = pListHead;;
        while(idx--){
            p = p->next;
        }
        return p;
    }
};

• 方法二，两个指针

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead == NULL) return NULL;
        ListNode* p = pListHead;
        ListNode* p1 = pListHead;
        while(--k && p->next){
            p = p->next;
        }
        if(k > 0) return NULL;
        while(p->next){
            p = p->next;
            p1 = p1->next;
        }
        return p1;
    }
};