单链表的逆置（带头结点）_单链表中头结点c程序

单链表逆置方法1

 使用三个指针
 时间复杂度：O（n)
 空间复杂度：O（1）
1
2
3

void ReverseList(LinkList head)
{
	assert(head != NULL);
	if (head->next == NULL || head->next->next == NULL)
	{
		return;
	}
	ListNode* pre = NULL, *s = NULL;
	ListNode* p = head->next;
	while (p != NULL)
	{
		s = p;
		p = p->next;
		s->next = pre;
		pre = s;
	}
	head->next = pre;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

单链表逆置方法2

使用两个指针（头插法）
时间复杂度：O（n)
空间复杂度：O（1）
1
2
3

void ReverseList(LinkList head)
{
	assert(head != NULL);
	if (head->next == NULL || head->next->next == NULL)
	{
		return;
	}
	ListNode* s = NULL, * p = head->next;
	head->next = NULL;
	while (p != NULL)
	{
		s = p;
		p = p->next;
		s->next = head->next;
		head->next = s;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

单链表逆置方法3

用栈实现（使用一个指针）
时间复杂度：O（n)
空间复杂度：O（n)
1
2
3

void ReverseList(LinkList head)
{
	assert(head != NULL);
	if (head->next == NULL || head->next->next == NULL)
	{
		return;
	}
	int len 0;
	ListNode* p = head->next;
	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	int* stack = (int*)malloc(sizeof(int) * len);
	int top = -1;
	p = head->next;
	while (p != NULL)
	{
		top += 1;
		stack[top] = p->data;
		p = p->next;
	}
	p = head->next;
	while (p != NULL)
	{
		p->data = stack[top];
		top = top - 1;
		p = p->next;
	}
	free(stack);
	stack = NULL;
}

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

单链表逆置方法4

递归
时间复杂度：O（n)
空间复杂度：O  (n)
1
2
3

ListNode* Reverse(ListNode* p)
{
	if (p == NULL || p->next == NULL)
	{
		return p;
	}
	ListNode* firstnode = Reverse(p->next);
	p->next->next = p;
	p->next = NULL;
	return firstnode;
}
void ReverseList(LinkList head)
{
	assert(head != NULL);
	ListNode* p = head->next;
	head->next = Reverse(p);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18