单链表的逆置(C++实现)

  单链表以及逆置是什么就不说了,就简单说一下思想:

链表的初始状态:

在这里插入图片描述

具体的方法就是将头节点后面的节点,依次通过指针指向,插入head头节点之后,即可完成逆置过程. 
示意图(这里我写一下中间处理流程,因为这样比较直观.第一次的处理与正常处理雷同):
在这里插入图片描述

需要注意的主要有两点:

1. 逆置之后的链表的尾部要NULL.在这里就是刚开始的时候的pHead->next->next = nullptr,具体可参考实现代码.
2. 当curr指向最后一个节点时,需要特殊处理一下.

实现代码:

#include <iostream>
using namespace std;
template <typename T>
struct Node
{
    Node(T t)
    {
        data = t;
    }
    T data;
    Node *next;
};

template <typename T>
class List
{
  public:
    List()
    {
        CreatList();
    }
    ~List()
    {
        Node<T> *start = head;
        Node<T> *end = start->next;
        while (end)
        {
            delete start;
            start = end;
            end = end->next;
        }
        delete start;
    }
    void CreatList()
    {
        head = new Node<T>(-100);
        Node<T> *temp = nullptr;
        rear = head;
        for (int i = 0; i < 10; i++)
        {
            temp = new Node<T>(i);
            temp->next = nullptr;
            rear->next = temp;
            rear = temp;
        }
        rear->next = nullptr;
    }
    void ReverseList()
    {
        Node<T> *curr, *beh;
        curr = head->next;
        rear = head->next;
        beh = curr->next;

        while (beh)
        {
            curr->next = head->next;
            head->next = curr;

            curr = beh;
            beh = beh->next;
        }
        curr->next = head->next;/*处理`curr`指向最后一个节点*/
        head->next = curr;
        /*处理链表的尾部 nullptr */
        rear->next = nullptr;
    }
    void Print()
    {
        Node<T> *temp = head->next;
        while (temp)
        {
            std::cout << temp->data << "  ";
            temp = temp->next;
        }
        std::cout << std::endl;
    }

  private:
    Node<T> *head;
    Node<T> *rear;
};

int main(void)
{
    List<int> list;
    list.Print();

    list.ReverseList();
    list.Print();
 }

运行结果:

在这里插入图片描述

附录:顺便用一下valgrind这个内存检测工具

我们去掉析构函数,并使用:

valgrind --tool=memcheck --leak-check=full --show-reachable=yes --trace-children=yes ./a.out

其中–leak-check=full 指的是完全检查内存泄漏,

–show-reachable=yes是显示内存泄漏的地点,

–trace-children=yes是跟入子进程。

得到的结果如下:
在这里插入图片描述

我们可以看到,在HEAP SUMMARY中显示申请了13个,但是只释放了2两个,这与我们的11个节点没释放,正好对应.

成功delete时:

在这里插入图片描述

原文链接: https://www.cnblogs.com/Tattoo-Welkin/p/10335251.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

    单链表的逆置(C++实现)

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/286586

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月15日 上午9:27
下一篇 2023年2月15日 上午9:29

相关推荐