研发埠

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

作者: 陈荣莲 时间: 2013-8-16 10:50
标题: [Microsoft面试]题目：输入一个单向链表，输出该链表中倒数第k 个结点。（链表的倒数第0 个结点为链表的尾指针）
链表结点定义如下：struct ListNode{int m_nKey;ListNode* m_pNext;};

作者: 秦静静 时间: 2013-8-16 11:09
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;}

欢迎光临研发埠 (http://bbs.yanfabu.com/)