单向链表反转是一道经典的求职面试笔试或机试题。给定如下如下链表的节点定义:
struct LinkNode
{
int value;
LinkNode* next;
};
比如有一个链表是这样的,1->2->3->4->5,反转后成为 5->4->3->2->1。请实现函数
LinkNode* Reverse(LinkNode* header);
实现链表反转,我们需要从第二个节点开始遍历,将当前节点的 next 指向前一个节点。这里需要注意的是,该变当前节点的 next 时,需要提前保存 next,不然遍历就会中断。
时间复杂度 O(n); 空间复杂度 O(1)。
//@brief: 迭代方式,实现单向链表反转
LinkNode* Reverse(LinkNode* header)
{
if (header == NULL || header->next == NULL)
{
return header;
}
LinkNode* pre = header, *cur = header->next;
pre->next = NULL;
while(cur != NULL)
{
auto next = cur-> next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
//
//@brief: main.cpp
//
#include <iostream>
using namespace std;
//@brief: 打印单向链表
void printLink(LinkNode* header)
{
while(header != NULL)
{
cout<< header->value;
header = header->next;
if (header != NULL)
{
cout<< "->";
}
}
cout<<endl;
}
int main(int argc, char* argv[])
{
//创建单向链接
LinkNode* header = NULL, *cur = NULL;
for(int i = 1; i <= 5; ++i)
{
LinkNode* node = new LinkNode;
node->value = i;
node->next = NULL;
if (header == NULL)
{
header = node;
cur = header;
}
else
{
cur->next = node;
cur = node;
}
}
printLink(header);
//反转单向链表
auto newHeader = Reverse(header);
printLink(newHeader);
}
编译执行输出:
g++ -std=c++11 main.cpp
./a.out
1->2->3->4->5
5->4->3->2->1
从倒数第二个节点开始反转,依次向前,将后一个节点的 next 指向当前节点。注意每次反转后要将当前节点的 next 置空,表示断开当前节点与后一个节点的关联。此种方法可以使用递归来实现。
时间复杂度 O(n); 空间复杂度 O(n)。
由于每次递归都需要为实参分配空间,所以相较于非递归实现,较为耗费栈空间,且不易理解。
//@brief: 递归方式,实现单链表反转
LinkNode * Reverse(LinkNode * head)
{
//递归终止条件:找到链表最后一个结点
if (head == NULL || head->next == NULL)
{
return head;
}
LinkNode * newhead = ReverseList(head->next); //先递后归,从后往前遍历每个节点进行反转
head->next->next = head; //将当前节点的后一个节点的 next 指向当前结点
head->next = NULL; //断开当前节点指向后一个节点
return newhead;
}