数据结构：单链表的逆置_单链表逆置

单链表的逆置

单链表的逆置：

方法一：向后转，第一个点变为最后一个，时间复杂度O(n)
(1):将第一个点置空

(2)：再创建一个指针s指向还未处理的结点的第一个

(3)再p赋值为q，q赋值为s，s赋值为q->next,再把p的值赋值给p->next,一直走下去，q==NULL,plist->next=p;结束


代码实现：

void Reverse2(List plist)
{
	if (plist==NULL||plist->next==NULL||plist->next->next==NULL)
	{
		return;
	}
	Node *p = plist->next;
	Node *q = p->next;
	Node *s;
	p->next = NULL;//一定要置空
	
	while (q!=NULL)
	{
		s = q->next;
		q->next = p;
		p = q;
		q = s;
	}
	plist->next = p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法二：利用头插的思想,把所有的结点断开，再利用头插方式把所有的结点重新插一次
（1）把plist置空,成为新的链

(2)把p头插到这条新链中，新的链与后面无关 p->next = plist->next;plist->next = p;p->q;q再指向下一个点


(3)再把p头插，重复头插

代码实现：

void Reverse(List plist)//逆置
{
	if (plist==NULL||plist->next==NULL||plist->next->next==NULL)
	{
		return ;
	}

	Node *p = plist->next;
	plist->next = NULL;

	Node *q;
	while (p!=NULL)
	{
		q = p->next;
		p->next = plist->next;
		plist->next = p;
		p = q;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19