数据结构与算法笔记（三）反转部分链表

╰半夏微凉° 2022-09-24 13:21 191阅读 0赞

# 反转部分链表 #

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

上次我们搞定了反转单向链表和双向链表的问题，但实际过程中我们可能只要反转部分链表，在这种情况下我们需要对上次写出的类增加一个叫做reverse\_part\_linklist的函数,传入参数为两个整数from和to，将from到to之间的节点进行反转

## 反转部分单向链表 ##

### 函数的设计思路主要有3点： ###

#### 1.判断传入的参数是否满足1≤from≤to≤N,若不满足直接返回。 ####

#### 2.正如上篇博客所讲对链表进行插入删除必须要找到其相邻的节点，因此我们要找到第from-1个节点fPre和第to+1个节点tPos。 ####

#### 3.在对链表处理时要时刻关注是否包含头节点，如果fPre为null那么我们要反转的部分包含头节点，那么我们要将头节点赋为未反转前反转部分的最后一个节点；如果fPre不为null，则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;
        }
        void reverse_part(int from, int to) {
            int len = 0;   // 链表的长度
            if (from > to || from  < 1) {
                return;    // 判断条件1
            }
    
    
            node* tempnode = head;
            node* fPre = NULL;
            node* tPos = NULL;
            while (tempnode != NULL) {
                len++;
                fPre = len == from-1 ? tempnode : fPre;  // 如果到了from-1，则将当前节点赋给fPre
                tPos = len == to+1 ? tempnode : tPos; // 如果到了to+1, 则将当前节点赋给tPos
                tempnode = tempnode->next;
            }
    
            if (to > len) {
                return ;    // 判断条件2
            }
    
            tempnode = fPre == NULL ? head : fPre->next;
    
            node * tempnode2 = tempnode->next;
    
            tempnode->next = tPos;
            node * next = NULL;
    
            while (tempnode2 != tPos) {
                next = tempnode2->next;
                tempnode2->next = tempnode;
                tempnode  = tempnode2;
                tempnode2 = next;  // 这里与反转链表写法类似
            }
    
            if (fPre != NULL) {
                fPre->next = tempnode;
                return ;
            }
    
            head = tempnode;
        }
    
    };
    int main() {
        linklist l;
        int cnt;
        cin >> cnt;
        for (int i = 0; i < cnt; i++) {
            l.add(i);
        }
        l.print();
        l.reverse_part(1,3);
        l.print();
        return 0;
    }

## 将1到3部分进行反转，运行截图如下： ##

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

# 这两次我们主要讲了反转链表，下期链表博客我们准备好来处理特定的链表删除吧哈哈！ #

[20160803101555467]: /images/20220719/89f1c09977224c82bc1a4e70a4bae710.png