链表逆置算法总结_数据结构链表逆置算法头插尾插

01.有头节点的单链表

【方法1】头插法

LNode *Inverse(LNode *L){
	LNode *p, *q;
	p = L->next;
	L->next = NULL;
	while (p != NULL){
		q = p;
		p = p->next;
		q->next = L->next;
		L->next = q;
	}
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12

The best preparation for tomorrow is doing your best today.
对明天做好的准备就是今天做到最好！

【方法2】修改指针的指向（三指针法）
见无头结点方法1

【方法3】利用栈的特性
将节点全部压入栈中，再将节点从栈弹出用尾插法重新构建链表。

02.无头节点的单链表（原地工作）

【方法1】修改指针的指向（三指针法）
思想：新建三个指针pslow,pmid,pfast,pslow指向NULL,pmid和pfast指向首节点，让pfast往后移动，修改指针指向，让pmid指向pslow;然后让pslow和pmid同步往后移动，循环操作，当pfast指向NULL时，单链表就已经逆置了。pmid指向新链表的首节点。

初始状态

pfast往后移动

修改指针指向

	void Reverse(Plist *pHead){
	pList pFast = *pHead;//pHead为首节点
	pList pMiddle = *pHead;
	pList pSlow = NULL;
	while (pFast)
	{
		pFast = pFast->_pNext;
		pMiddle->_pNext = pSlow;
		pSlow = pMiddle;
		pMiddle = pFast;
	}
	*pHead = pMiddle;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

【方法2】利用栈的特性