面试题15:链表中倒数第K个节点

题目:输入一个链表,输出该链表中倒数第K个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第一个节点。

链表的定义如下:

1
2
3
4
5
6
7
struct ListNode{
int value;
ListNode* next;
ListNode(int data=int()):value(data),next(NULL)
{}
};


分析

有三种方法:递归法,自定义栈法和前后指针法。

递归法

代码如下:

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
28
29
30
ListNode* _FindKthToTail(ListNode* head,int& k)
{
if(head==NULL)
{
return NULL;
}
else
{
ListNode* tmp=_FindKthToTail(head->next,k);
if(k==0)
return tmp;
}
if(k==1)
{
k=0;
return head;
}
else if(k>1)
k--;
}
ListNode* FindKthToTail(ListNode* head,int k)throw(ListIsTooShort)
{
ListNode* tmp=_FindKthToTail(head,k);
if(k==0)
return tmp;
else
throw ListIsTooShort();
}

自定义栈法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* FindKthToTail(ListNode* head,int k)throw(ListIsTooShort)
{
if(head==NULL || k<=0)
return NULL;
stack<ListNode*> s;
while(head!=NULL)
{
s.push(head);
head=head->next;
}
while(--k!=0 && !s.empty())
{
s.pop();
}
if(k==0)
return s.top();
else
throw ListIsTooShort();
}

前后指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ListNode* FindKthToTail(ListNode* head,int k)throw(ListIsTooShort)
{
if(head==NULL || k==0)
return NULL;
ListNode* front=head,*last=head;
while(k-->0 && front!=NULL)
{
front=front->next;
}
if(k>0)
{
throw ListIsTooShort();
}
else
{
while(front!=NULL)
{
front=front->next;
last=last->next;
}
}
return last;
}

这三种方法的优缺点如下:

<table> <thead> <tr> <th align="center"></th> <th align="center">时间复杂度</th> <th align="center">空间复杂度</th> <th align="center">是否最优</th> </tr> </thead> <tbody> <tr> <td align="center">递归法</td> <td align="center">O(n)</td> <td align="center">O(n)</td> <td align="center">否</td> </tr> <tr> <td align="center">自定义栈法</td> <td align="center">O(n)</td> <td align="center">O(n)</td> <td align="center">否</td> </tr> <tr> <td align="center">前后指针法</td> <td align="center">O(n)</td> <td align="center">O(1)</td> <td align="center">是</td> </tr> </tbody> </table>

因此,最好的方法是最后一种。

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往