【剑指Offer】【链表】链表中倒数第k个结点

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

A1：先从头到尾扫描链表，得到链表的总长度n，然后再扫描一次链表，输出n-k+1处的结点 ===> 测试用例超时

A2：创建两个指针，一个遍历链表到k处，若链表已指向空，则返回false

　　到k处后，进入第二个循环，指针A与指针B一起向后移动，当指针A指向nullptr时返回，结果为指针B指向的结点

　　因为指针A和指针B一直保持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 == nullptr) || (k < 1))

		{

			return nullptr;

		}

		ListNode* pNodeA = pListHead;

		ListNode* pNodeB = pListHead;

		while (k > 0)

		{

			if (pNodeA == nullptr)

			{

				return nullptr;

			}

			pNodeA = pNodeA->next;

			k--;

		}

		while (pNodeA != nullptr)

		{

			pNodeA = pNodeA->next;

			pNodeB = pNodeB->next;

		}

		return pNodeB;

    }

};

//这个解法，是两个指针距离保持在k-1的，在VS下成功通过，但是在牛客编辑器中说有段错误，很奇怪

//和上一个解法差不多相同

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

		if ((pListHead == nullptr) || (k < 1))

		{

			return nullptr;

		}

		ListNode* pNodeA = pListHead;

		ListNode* pNodeB = pListHead;

		ListNode* pNodeA = pListHead;

		ListNode* pNodeB = pListHead;

		while (k > 1)

		{

			if (pNodeA == nullptr)

			{

				return nullptr;

			}

			pNodeA = pNodeA->next;

			k--;

		}

		while (pNodeA->next != nullptr)

		{

			pNodeA = pNodeA->next;

			pNodeB = pNodeB->next;

		}

		return pNodeB;

        }

巴特西

【剑指Offer】【链表】链表中倒数第k个结点

最新文章

热门文章