2013
12-13

# 面试题精选100题(09)－链表中倒数第k个结点[数据结构]

struct ListNode
{
int       m_nKey;
ListNode* m_pNext;
};

///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
//        k         - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k)
{
return NULL;

// count the nodes number in the list
unsigned int nNum = 0;
while(pCur->m_pNext != NULL)
{
pCur = pCur->m_pNext;
nNum ++;
}

// if the number of nodes in the list is less than k
// do nothing
if(nNum < k)
return NULL;

// the kth node from the tail of a list
// is the (n - k)th node from the head
for(unsigned int i = 0; i < nNum - k; ++ i)
pCur = pCur->m_pNext;

return pCur;
}


///////////////////////////////////////////////////////////////////////
// Find the kth node from the tail of a list
//        k         - the distance to the tail
// Output: the kth node from the tail of a list
///////////////////////////////////////////////////////////////////////
ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k)
{
return NULL;

ListNode *pBehind = NULL;

for(unsigned int i = 0; i < k; ++ i)
{
else
{
// if the number of nodes in the list is less than k,
// do nothing
return NULL;
}
}

// the distance between pAhead and pBehind is k
// when pAhead arrives at the tail, p
// Behind is at the kth node from the tail
{
pBehind = pBehind->m_pNext;
}

return pBehind;
}


1. int half(int *array,int len,int key)
{
int l=0,r=len;
while(l<r)
{
int m=(l+r)>>1;
if(key>array )l=m+1;
else if(key<array )r=m;
else return m;
}
return -1;
}
这种就能避免一些Bug
l,m,r
左边是l,m;右边就是m+1,r;

2. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

3. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。