题目描述:
输入一个链表,输出该链表中倒数第k个结点。
解题思路:
时间复杂度:$O(n)$, 空间复杂度:$O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
class { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode *p = pListHead; ListNode *q = pListHead; int i = 0; for( ;p != NULL;i++) { if(i >= k) q = q -> next; p = p -> next; } return i < k?NULL:q; } };
|
解题思路二:
时间复杂度:$O(n)$, 空间复杂度:$O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
class { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { ListNode *p = pListHead; ListNode *q = pListHead; while(p && k > 0 ) { p = p -> next; k--; } while(p) { p = p -> next; q = q -> next; } return k > 0 ? NULL:q; } };
|
近期评论