【PTA数据结构】6-5 链表逆置（两种方法）_数据结构单链表逆置pta

本题要求实现一个函数，将给定单向链表逆置，即表头置为表尾，表尾置为表头。

链表结点定义如下：

struct ListNode {
    int data;
    struct ListNode *next;
};
1
2
3
4

函数接口定义：

struct ListNode *reverse( struct ListNode *head );
1

其中head是用户传入的链表的头指针；函数reverse将链表head逆置，并返回结果链表的头指针。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *createlist(); /*裁判实现，细节不表*/
struct ListNode *reverse( struct ListNode *head );
void printlist( struct ListNode *head )
{
     struct ListNode *p = head;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode  *head;

    head = createlist();
    head = reverse(head);
    printlist(head);

    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

输入样例：

1 2 3 4 5 6 -1
结尾无空行

输出样例：

6 5 4 3 2 1
结尾无空行

解答：

//方法一：一般方法（if判断插入的结点是不是头结点）
struct ListNode *reverse(struct ListNode *head)
{
	//用头插法新建一个不包含头结点的链表，原来的链表按照顺序依次给新链表赋值
	struct ListNode *L, *old, *s;
	L = NULL;
	old = head;
	while (old)
	{
		s = (struct ListNode*) malloc(sizeof(struct ListNode));
		s->data = old->data;//讲老链表当前值赋给新结点
		old = old->next;//老链表指针往后移
		if (L == NULL)
		{
			//如果s是新链表的第一个结点
			L = s;
			s->next = NULL;
		}
		else
		{
			s->next = L;
			L = s;//新结点给到新链表上
		}
	}
	free(head);
	return L;
}

//方法二：虚拟头结点（会浪费一个结点的空间）
struct ListNode *reverse(struct ListNode *head)
{
	//用头插法新建一个链表，原来的链表按照顺序依次给新链表赋值
	struct ListNode *L, *old, *s;
	L = (struct ListNode*) malloc(sizeof(struct ListNode));
	L->next = NULL;
	old = head;
	while (old)
	{
		s = (struct ListNode*) malloc(sizeof(struct ListNode));
		s->data = old->data;//讲老链表当前值赋给新结点
		old = old->next;//老链表指针往后移
		s->next = L->next;
		L->next = s;//新结点给到新链表上
	}
	L = L->next;//把头结点抛弃掉（浪费一个结点的空间，但是代码会更简洁）
	free(head);
	return L;
}
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