反转链表-白红宇

反转链表

阅读量：5034 次

发布时间：2019-06-12

本文共 1136 字，大约阅读时间需要 3 分钟。

又见翻转链表，这回是给定接口的递归和非递归翻。比反转链表多了接口限制。

#include 
 
using namespace std;
 
typedef struct node LinkNode;
struct node
{
int data;
LinkNode *next;
};
 
LinkNode *reverse_link(LinkNode *head)
{
if (head == NULL) return NULL;
 
LinkNode *prev = NULL, *next = head->next;
 
while (next != NULL)
{
head->next = prev;
prev = head;
head = next;
next = head->next;
}
 
head->next = prev;
 
return head;
}
 
LinkNode *reverse_link_recursive(LinkNode *head)
{
if (head == NULL) return NULL;
if (head->next == NULL) return head;
 
LinkNode *next = head->next;
LinkNode *reverse_head = reverse_link_recursive(next);
next->next = head;
head->next = NULL;
 
return reverse_head;
}
 
void print_link(const LinkNode *head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
 
cout << endl;
}
 
int main()
{
LinkNode o[6];
 
for (int i = 0; i < 5; ++i)
{
o[i].data = i;
o[i].next = &o[i + 1];
}
o[4].next = NULL;
 
print_link(&o[0]);
LinkNode *head = reverse_link(&o[0]);
print_link(head);
head = reverse_link_recursive(head);
print_link(head);
 
return 0;
}