文章目录

前言1.头插法2.就地逆置法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; //新链表头永远指向的是原链表的链尾 }

---

总结

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