LeetCode_C/206_Reverse_Linked_List.c at master · lph12168/LeetCode_C · GitHub

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
/*
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
*/

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

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

// 不带头结点公用函数
struct ListNode* initList()
{
	struct ListNode* list = (struct ListNode*)malloc(sizeof(struct ListNode));

	list->val = -1;
	list->next = NULL;
	return list;
}
void insertList(struct ListNode* l, int val)
{
	struct ListNode* list = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* t = l;

	if (!t)
		return;
	while (t->next)
		t = t->next;
	list->val = val;
	list->next = NULL;
	t->next = list;
}
void assignList(struct ListNode* l, int *val, int len)
{
	int i;

	if (len > 0)
		l->val = val[0];
	for (i = 1; i < len; i++)
		insertList(l, val[i]);
}
void printList(char *name, struct ListNode* l)
{
	struct ListNode* t = l;

	printf("%s = [", name);
	while (t) {
		if (t->next)
			printf("%d, ", t->val);
		else
			printf("%d", t->val);
		t = t->next;
	}
	printf("]\n");
}
/* 以上是公用部分 */

// while循环体使用t->next，最后一个节点需要单独处理
struct ListNode* reverseList1(struct ListNode* head) {
	struct ListNode* t = head;
	struct ListNode* pre = NULL;
	struct ListNode* next;

	if (!t)
		return NULL;

	while (t->next) {
		next = t->next;
		t->next = pre;
		pre = t;
		printf("t = %d, pre = %d, next = %d\n", t->val, pre->val, next->val);
		t = next;
	}
	t->next = pre;
	printf("t = %d, pre = %d, next = %d\n", t->val, pre->val, next->val);

	return t;
}

// while循环体使用t，t在最后会变成空指针而需要返回pre
struct ListNode* reverseList(struct ListNode* head) {
	struct ListNode* t = head;
	struct ListNode* pre = NULL;
	struct ListNode* next;

	if (!t)
		return NULL;

	while (t) {
		next = t->next;
		t->next = pre;
		pre = t;
		printf("t = %d, pre = %d, next = %d\n", t->val, pre->val, next != NULL ? next->val : 0);
		t = next;
	}

	return pre;
}

// 递归，官方答案，还未理解
struct ListNode* recursive_reverseList(struct ListNode* head) {

	if (head == NULL || head->next == NULL) {
		return head;
	}

	struct ListNode *newHead = recursive_reverseList(head->next);
	head->next->next = head;
	head->next = NULL;

	return newHead;
}

void main()
{
	struct ListNode* list_in = initList();
	struct ListNode* list_out = NULL;
	int input_array[] = {1, 2, 3, 4, 5};
	int len = sizeof(input_array) / sizeof(input_array[0]);

	assignList(list_in, input_array, len);
	printList("list_in", list_in);
	list_out = reverseList(list_in);
	printList("list_out", list_out);
}