社区 › 研发应用 › [Microsoft面试]题目：输入一个单向链表，输出该链表中倒数第k 个结点。（链表的倒数第0 个结点为链表的尾指针）

陈荣莲 发表于 2013-8-16 10:50:27

[Microsoft面试]题目：输入一个单向链表，输出该链表中倒数第k 个结点。（链表的倒数第0 个结点为链表的尾指针）

链表结点定义如下：struct ListNode{int m_nKey;ListNode* m_pNext;};

秦静静 发表于 2013-8-16 11:09:06

Two ways. 1:record the length of the linked list, then go n-k steps. 2: use two cursors.Time complexities are exactly the same.Node * lastK(Node * head, int k) {if (k<0) error(“k < 0”);Node *p=head, *pk=head;for (;k>0;k--) {    if (pk->next!=NULL) pk =pk->next;    else return NULL;}while (pk->next!=NULL) {    p=p->next, pk=pk->next;}return p;}

查看完整版本: [Microsoft面试]题目：输入一个单向链表，输出该链表中倒数第k 个结点。（链表的倒数第0 个结点为链表的尾指针）