单链表实现反转的三种方法_单链表反转三种方法

单链表的操作是面试中经常会遇到的问题，今天总结一下反转的几种方案：

1 ，两两对换
2， 放入数组，倒置数组
3， 递归实现

代码如下：

#include<stdio.h>
#include<malloc.h>
typedef struct Node
{
    int data;
    struct Node *pnext;
} Node,*pnode;
pnode CreateNode()
{
    pnode phead=(pnode)malloc(sizeof(Node));
    if(phead==NULL)
    {
        printf("fail to allocate memory");
        return -1;
    }
    phead->pnext=NULL;
    int n;
    pnode ph=phead;
    for(int i=0; i<5; i++)
    {
        pnode p=(pnode)malloc(sizeof(Node));
        if(p==NULL)
        {
            printf("fail to allocate memory");
            return -1;
        }
        p->data=(i+2)*19;
        phead->pnext=p;
        p->pnext=NULL;
        phead=phead->pnext;
    }
    return ph;
}
int list(pnode head)
{
    int count=0;
    printf("遍历结果：\n");
    while(head->pnext!=NULL)
    {
        printf("%d\t",head->pnext->data);
        head=head->pnext;
        count++;
    }
    printf("链表长度为：%d\n",count);
    return count;
}
pnode reverse2(pnode head)//两两节点之间不断交换
{
   if(head == NULL || head->next == NULL)
   return head;
   pnode pre = NULL;
   pnode next = NULL;
   while(head != NULL){
	   next = head->next;
	   head->next = pre;
	   pre = head;
	   head = next;
}
	return pre;
}
void reverse1(pnode head,int count)//把链表的节点值放在数组中，倒置数组
{
    int a[5]= {0};

    for(int i=0; i<count,head->pnext!=NULL; i++)
    {
        a[i]=head->pnext->data;
        head=head->pnext;

    }
    for(int j=0,i=count-1; j<count; j++,i--)
        printf("%d\t",a[i]);
}

pnode reverse3(pnode pre,pnode cur,pnode t)//递归实现链表倒置
{
    cur -> pnext = pre;
    if(t == NULL)
        return cur;   //返回无头节点的指针，遍历的时候注意
    reverse3(cur,t,t->pnext);
}

pnode new_reverse3(pnode head){  //新的递归转置

	if(head == NULL || head->next == NULL)
		return head;
	pnode new_node = new_reverse3(head->next);
	head->next->next = head;
	head->next = NULL;
	return new_node;  //返回新链表头指针
}
int main()
{
    pnode p=CreateNode();
    pnode p3=CreateNode();
    int n=list(p);
    printf("1反转之后：\n");
    reverse1(p,n);
    printf("\n");
    printf("2反转之后：\n");
    pnode p1=reverse2(p);
    list(p1);
    p3 -> pnext = reverse3(NULL,p3 -> pnext,p3->pnext->pnext);
    printf("3反转之后：\n");
    list(p3);
    free(p);
    free(p1);
    free(p3);
    return 0;
}


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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

毫无疑问，递归是解决的最简单方法，四行就能解决倒置问题。
思路参考：http://blog.csdn.net/feliciafay/article/details/6841115

这里注意： head ->next = pre; 以及 pre = head->next，前者把head->next 指向 pre，而后者是把head->next指向的节点赋值给pre。如果原来head->next 指向 pnext节点，前者则是head重新指向pre，与pnext节点断开，后者把pnext值赋值给pre，head与pnext并没有断开。