面试题16:反转链表

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。链表定义如下:

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


此题可以用递归和头插法来做。

递归

用递归做起来稍微复杂一点,而且会有个问题,就是当链表太长时,可能会导致系统栈溢出。

大体思路就是,当我们每递归的链表的一个节点时,如果该节点不是最后一个,就先递归反转它后面的链表,然后将该节点push_back到尾部,所以我们需要一个tail指针来表明最后一个节点。否则return即可。

代码如下:

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
ListNode* _ReverseList(ListNode* head,ListNode*& tail)
{
if(head==NULL)
return NULL;
if(head->next==NULL)
{
tail=head;
return head;
}
ListNode* tmp=_ReverseList(head->next,tail);
tail->next=head;
tail=tail->next;
return tmp;
}
ListNode* ReverseList(ListNode* head)
{
if(head==NULL)
return NULL;
ListNode* tail=NULL;
ListNode* tmp=_ReverseList(head,tail);
tail->next=NULL;
return tmp;
}

头插法

这种方法的思想就是,我们从链表的第二个节点开始(如果有的话),一次摘取当前节点并头插到前面已经部分反转的链表中去。需要注意的是,我们要维护三个节点指针,分别指向已经部分反转的链表头、当前节点和当前节点的下一个节点。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* ReverseList(ListNode* head)
{
if(head==NULL)
return NULL;
ListNode* cur=head->next;
head->next=NULL;
ListNode* next=NULL;
while(cur!=NULL)
{
next=cur->next;
cur->next=head;
head=cur;
cur=next;
}
return head;
}

以上

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

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