单链表(原地)逆置 |
您所在的位置：网站首页 › python单链表的逆置头插法完整代码 › 单链表(原地)逆置 |
单链表(原地)逆置
|
单链表实现逆置
从头遍历链表，使每一个结点都指向该结点的上一个节点。最后再处理头结点与为结点即可。 三个指针对于一个单链表来说，我们不可能从一个结点(Node *i )找到它的上一个节点，所以我们需要额外定义一个指针(Node *s )指向该结点的上一个结点。此外在改变当前结点next指针的指向时会断开与下一结点的连接，所以我们还需要一个指针(Node *t )指向当前结点的下一个结点。
如图所示： i 指向当前结点，改变当前结点next 指向，同时自动与其后续结点断开； s 初始为空，代表尾结点指向NULL，随着i 的移动，s 指向新链表的头； t 指向 i 的下一个结点，以便在单链表断开的情况下还能继续遍历链表。 代码如下： //单链表逆置 void Reverse(LNode* List) { LNode* s = nullptr;//空指针 //开始时为空指针，循环时成为新链表的头(类似头插) LNode* i = nullptr; //遍历链表，改变指针(next)指向 LNode* t = List->next; //保留断开处的链表 while (t != nullptr) { i = t; t = t->next; //保存断开处的地址 i->next = s; //改变当前结点指向 s = i; } List->next = s; //头结点 }
|
【本文地址】
今日新闻 |
推荐新闻 |