如何实现链表的逆序？

轩辕小不懂发布于 2022-03-24 16:26

阅读 538

答案 1

分类：人工智能

人工智能

python

编程论坛

给定一个带头结点的单链表，请将其逆序。即如果单链表原来为head-＞1-＞2-＞3-＞4-＞5-＞6-＞7，那么逆序后变为head-＞7-＞6-＞5-＞4-＞3-＞2-＞1。

最佳答案 2022-03-25 17:15

3370

Nen 2022-03-24 17:06

- 程序员

分析与解答：

由于单链表与数组不同，单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。在对链表的操作过程中，需要特别注意在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。

方法一：就地逆序主要思路为：在遍历链表的时候，修改当前结点的指针域指向，让其指向它的前驱结点。为此需要用一个指针变量来保存前驱结点的地址。此外，为了在调整当前结点指针域的指向后还能找到后继结点，还需要另外一个指针变量来保存后继结点的地址，在所有的结点都被保存好以后就可以直接完成指针的逆序了。除此之外，还需要特别注意对链表首尾结点的特殊处理。