单链表的逆置方法

前言

单链表的逆置方法有很多种，此文简要说明以下三种方法

---

1.头插法

主要思路：遍历的过程中，将遍历的每一个元素依次插入到表头header之后

代码如下：

void ReverseList(LinkList& head)
{
	LinkList p,q;
	p = head->next;
	head->next = NULL;
	while (p)
	{
		q = p;
		p = p->next;
		q->next = head->next;
		head->next = q;
		
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.就地逆置法

主要思路：重新创建一个新表，遍历链表依次将元素插入到新表的头结点

代码如下：

void ReverseList(LinkList& L)
{
	LinkList cur ,newlist, p;
	cur = L->next;
	newlist = NULL; 
	while(cur)
	{
		p = cur;
		cur = cur->next;
		p->next = newlist;
		newlist = p; 
	}
	L = newlist;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.递归实现

代码如下（示例）：

Status ReverseList(ListLink L)
{
	LinkList p = L;
    if (p && p->next)       //链表为空直接返回，而H->next为空是递归基
        return p;
    LinkList q = ReverseList(p->next); //一直循环到链尾 
    p->next->next =  p;                    //翻转链表的指向
    p->next = NULL;                          //记得赋值NULL，防止链表错乱
    return q;                          //新链表头永远指向的是原链表的链尾
}
1
2
3
4
5
6
7
8
9
10

---

总结

头插法和就地逆置法的区别在于，逆置后的链表输出时，那么头插法是从head开始的，而就地逆置则是从表尾开始的。