数据结构与算法学习笔记(二)反转链表

梦里梦外; 2022-07-24 12:02 192阅读 0赞

# 反转链表 #

--------------------

好久没写博客了，这一年来学到了挺多的，数据结构和算法，计算机组成原理，操作系统，数据库，unity等等。最近放暑假就准备把博客接着搞下去，快来享受饕餮大餐吧！

## 反转单向链表和双向链表 ##

### 1.单向链表： ###

通常链表问题都会给一个链表的头结点head， 以及不同问题对应的其他参数，要求我们写出对应的函数来完成相应的功能。链表中最需要注意就是插入删除中指针的重连。对于反转单向链表以及双向链表，我们需要申请两个辅助指针一个pre和一个next指针， pre用来保存新链表最开始的位置而next用来保存不断移动的head指针下一个指针即需要处理的下一个指针位置。

#include <iostream>
    using namespace std;
    
    struct node {
        int data;
        node * next;
    };
    class linklist {
    private:
        node * head;
    
    public:
        linklist() {
            head = NULL; // 初始化head
        }
    
        void add(int d) {
            node *temp = head;
            node * newnode = new node();
            newnode->next = NULL;
            newnode->data = d;
            if (temp == NULL) {
                head = newnode;  // 对空链表的处理
                return;
            }
            while (temp->next != NULL) {
                temp = temp->next;  // 走到链表最后一个非空节点
            }
            temp->next = newnode;
        }
    
        void print() {
            node *temp = head;
            while (temp != NULL) {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << endl;
        }
    
        void reverse() {
            node* pre = NULL;  // 新链表的头结点
            node* next = NULL;  // 保存原链表要处理的下一个节点，防止丢失
            while (head != NULL) {
                next = head->next;
                head->next = pre;
                pre = head;
                head = next;
            }
            head = pre;
        }
    };
    int main() {
        linklist l;
        int cnt;
        cin >> cnt;
        for (int i = 0; i < cnt; i++) {
            l.add(i);
        }
        l.print();
        l.reverse();
        l.print();
        return 0;
    }

### 2.双向链表： ###

与单向链表同理，不过要注意双向链表不仅只有指向下一个元素的next指针还有指向上一个元素的last指针。

#include <iostream>
    using namespace std;
    
    struct node {
        int data;
        node * next;
        node *last;
    };
    class linklist {
    private:
        node * head;
    
    public:
        linklist() {
            head = NULL; // 初始化head
        }
    
        void add(int d) {
            node *temp = head;
            node * newnode = new node();
            newnode->next = NULL;
            newnode->data = d;
            if (temp == NULL) {
                newnode->last = NULL;
                head = newnode;  // 对空链表的处理
                return;
            }
            while (temp->next != NULL) {
                temp = temp->next;  // 走到链表最后一个非空节点
            }
            newnode->last = temp;  // 注意对last指针的重连
            temp->next = newnode;
        }
    
        void print() {
            node *temp = head;
            while (temp->next != NULL) {
                cout << temp->data << " ";
                temp = temp->next;
            }
            cout << temp->data << " ";
            cout << endl;
    
            //测试双向链表last是否正确
            while (temp->last != NULL) {
                cout << temp->data << " ";
                temp = temp->last;
            }
            cout << temp->data << " ";
            cout << endl;
    
            cout << endl;
        }
    
        void reverse() {
            node* pre = NULL;  // 新链表的头结点
            node* next = NULL;  // 保存原链表要处理的下一个节点，防止丢失
            while (head != NULL) {
                next = head->next;
                head->next = pre;
                head->last = next;
                pre = head;
                head = next;
            }
            head = pre;
        }
    };
    int main() {
        linklist l;
        int cnt;
        cin >> cnt;
        for (int i = 0; i < cnt; i++) {
            l.add(i);
        }
        l.print();
        l.reverse();
        l.print();
        return 0;
    }

## 运行截图如下： ##

![这里写图片描述][20160731093351746]

# 内容不宜过多，我们下期链表博客见！ #

[20160731093351746]: /images/20220722/cb24859d3aea4391a5df5e5f877e3b2e.png