剑指offer之链表中倒数第K个结点
链表中倒数第k个结点
https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking
题目
输入一个链表,输出该链表中倒数第k个结点。
解1
思路
解1是直观的方法,先遍历一遍链表获取链表长度n,然后在从头开始遍历到n-k+1处,需要遍历2n-k-2次。
代码
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { unsigned int NumOfNode = 1; if (k==0 || !pListHead) { return nullptr; } ListNode* pListTra = pListHead; while (NULL != pListTra->next) { NumOfNode++; pListTra = pListTra->next; } if (NumOfNode < k) { return nullptr; } else { for (unsigned int i = 0; i < NumOfNode - k; i++) { pListHead = pListHead->next; } return pListHead; } } };
解2
思路
解2是大佬的思路,举个例子有两条十米的跑道,有两位选手,让乙选手在倒数第三米处,也就是第八米处停住,方法是先让甲走到第三米处,然后两人以同样速度前进,当甲到终点时,乙刚好位于倒数第三米处,同样需要遍历2n-k-2次。
代码
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode *pLinked1 = pListHead, *pLinked2 = pListHead; if (k==0 || !pListHead) { return nullptr; } while (NULL != pLinked1->next && k-1) { pLinked1 = pLinked1->next; k--; } if (k - 1 > 0) { return nullptr; } else { while(pLinked1->next) { pLinked1 = pLinked1->next; pLinked2 = pLinked2->next; } return pLinked2; } } };