单链表反转（C语言）
方法一：三指针法
思路：
a,b,c三个指针分别指向三个位置
a指针和b指针用来反转两个结点
c指针指向下一个节点用来标记和向前推进
-
代码
//单链表反转函数 //三指针法 /* a,b,c三个指针分别指向三个位置， a指针和b指针用来反转两个结点， c指针指向下一个节点用来标记和向前推进。 */ list *reverse_ThreePoints1(list *head) { list *a,*b,*c; a = head; b = a->next; c = b; a->next = NULL; while(b != NULL) { c = c->next; b->next = a; a = b; b = c; } return a; } //三指针法优化 /* 说是优化，其实是一样的思路，只不过，这里的head作为b，a指向空。 a,b,head三个指针分别指向三个位置， a指针和head指针用来反转两个结点， b指针指向下一个节点用来标记和向前推进。 */ list *reverse_ThreePoints2(list *head) { list *a = NULL,*b = NULL; while(head != NULL) { b = head->next; head->next = a; a = head; head = b; } return a; }
方法二：回溯法（递归）
思路
-
当链表有两个结点时，直接进行反转即可
p->next->next = p; p->next = NULL; -
当链表两个以上结点时
指针向后遍历至最后两个结点，将最后两个反转
-
然后向前回溯，此时，由于后面的两个结点已经反转，所以，当前结点和后一个结点可以看成是最后两个结点，直接进行反转操作即可
p->next->next = p; p->next = NULL;
-
代码
//递归法 list *reverse_Recursive(list *head) { list *p; p = head; if(p->next == NULL) return head; if(p->next->next != NULL) { head = reverse_Recursive(p->next); p->next->next = p; p->next = NULL; } else { head = p->next; p->next->next = p; p->next = NULL; } return head; }
源代码
#include <stdio.h>
#include <malloc.h>
struct list
{
int data;
list *next;
};
list *init_list(list *head)
{
int i = 1;
list *p = head;
while(i <= 9)
{
list *s;
s = (list*)malloc(sizeof(list));
s->data = i;
s->next = NULL;
p->next = s;
p = p->next;
i++;
}
return head->next;
}
void print_list(list *head)
{
list *p;
p = head;
while(p != NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
//单链表反转函数
//三指针法
/*
a,b,c三个指针分别指向三个位置，
a指针和b指针用来反转两个结点，
c指针指向下一个节点用来标记和向前推进。
*/
list *reverse_ThreePoints1(list *head)
{
list *a,*b,*c;
a = head;
b = a->next;
c = b;
a->next = NULL;
while(b != NULL)
{
c = c->next;
b->next = a;
a = b;
b = c;
}
return a;
}
//三指针法优化
/*
说是优化，其实是一样的思路，只不过，这里的head作为b，a指向空。
a,b,head三个指针分别指向三个位置，
a指针和head指针用来反转两个结点，
b指针指向下一个节点用来标记和向前推进。
*/
list *reverse_ThreePoints2(list *head)
{
list *a = NULL,*b = NULL;
while(head != NULL)
{
b = head->next;
head->next = a;
a = head;
head = b;
}
return a;
}
//递归法
list *reverse_Recursive(list *head)
{
list *p;
p = head;
if(p->next == NULL)
return head;
if(p->next->next != NULL)
{
head = reverse_Recursive(p->next);
p->next->next = p;
p->next = NULL;
}
else
{
head = p->next;
p->next->next = p;
p->next = NULL;
}
return head;
}
int main()
{
list *head;
head = (list*)malloc(sizeof(list));
head = init_list(head);
print_list(head);
head = reverse_ThreePoints1(head);
print_list(head);
head = reverse_ThreePoints2(head);
print_list(head);
head = reverse_Recursive(head);
print_list(head);
return 0;
}
