3种单链表的逆置方法

链式存储结构一般有单链表、静态链表、循环链表和双向链表。那么，单链表的逆置方法有哪些？极悦小编来为大家解答。

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;		
	}
}

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;
}

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;                          //新链表头永远指向的是原链表的链尾
}

以上就是关于“3种单链表的逆置方法”介绍，大家如果想了解更多相关知识，可以关注一下极悦的Java堆栈，里面有更丰富的知识等着大家去学习，希望对大家能够有所帮助。