剑指Offer——链表中倒数第k个节点

Question

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

Solution

一种想法就是扫描两边，第一遍求出总的节点个数，第二遍从头开始走n-k个
第二种思想类似于fast-slow指针的方法，fast指针先走k-1步，让两个指针距离保持为k，然后在一起走，fast走到最后的时候，slow刚好走到倒数第k个节点。

Code

/*

struct ListNode {

	int val;

	struct ListNode *next;

	ListNode(int x) :

			val(x), next(NULL) {

	}

};*/

class Solution {

public:

    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

        // 不能改变链表的结构

        // 构造两个指针，他们的距离差为k，那么当第一个指针走到最后的时候，第二个指针刚好到第k个节点的位置

        if (pListHead == NULL || k == 0)

            return NULL;

        ListNode* p1 = pListHead;

        ListNode* p2 = pListHead;

		for (int i = 0; i < k - 1; i++) {

            if (p1->next != NULL)

                p1 = p1->next;

            else

                return NULL;

        }

        while (p1->next) {

            p1 = p1->next;

            p2 = p2->next;

        }

        return p2;

    }

    // 可以考虑扫描两遍，第一遍求个数，第二遍走n－k个

    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {

    	if (pListHead == NULL && k <= 0)

            return NULL;

        int num = 0;

        ListNode* tmp = pListHead;

        while (tmp) {

            num++;

            tmp = tmp->next;

        }

        if (num < k)

            return NULL;

        for (int i = 0; i < num - k; i++) {

        	pListHead = pListHead->next;

        }

        return pListHead;

    }

};

巴特西

剑指Offer——链表中倒数第k个节点

Question

Solution

Code

最新文章

热门文章