单链表逆序三种方法

发表于2023-12-14由Zeno Chen

定义结构体

typedef struct Node{
    int data;
    struct Node* next;
} Node,*pNode;

链表初始化

void initHead(pNode &head){
    head=new Node;
    head->next=NULL;
}

链表建立（尾插法）

void bulidHead(pNode &head){
    pNode tail=head;
    tail->next=NULL;
    for(int i=0;i<10;i++){      //将0~9插入链表
        pNode p=new Node;
        p->data=i;
        tail->next=p;
        tail=p;
        tail->next=NULL;
    }
}

链表打印

void printHead(pNode &head){
    pNode p=head->next;
    while(p){
        cout<<p->data<<" ";
        p=p->next;
    }
}

链表销毁

void destroyHead(pNode &head){
    pNode p=head;
    while(head){
        p=head->next;
        delete head;
        head=p;
    }
}

一、迭代法

需要三个指针，前驱p1，当前p2，后继p3

结束的条件是p2==null

带头节点

/**
 * 迭代法逆序[有头部]
 * @param head
 */
void reverse1(pNode &head){
    // 至少有除头节点以外两个节点才能逆序
    if(head->next!=NULL&&head->next->next!=NULL){
        // 缓存除了头以外的节点
        pNode p1=head->next,p2=head->next->next,p3=NULL;
        while(p2){
            // 获取循环P3+i节点
            p3=p2->next;
            // 设置二节点下一跳为前一个节点
            p2->next=p1;
            // 如果第一个节点是头的下一跳，置空
            // 防止形成环，只出现在第一个和第二个节点之间。要把循环去掉，否则打印时会出现死循环
            if(p1==head->next) {
                p1->next=NULL;
            }
            // 左移
            p1=p2;
            p2=p3;
        }
        //head变成新头节点返回
        head->next=p1;
    }
    else return;
}

不带头结点

/**
 * 迭代法逆序[无头部]
 * @param head
 */
void pNode reverse1(pNode head){
    // 至少有除头节点以外两个节点才能逆序
    if(head!=NULL&&head->next!=NULL){
        // 缓存节点
        pNode p1=head,p2=head->next,p3=NULL;
        while(p2){
            // 获取P3节点
            p3=p2->next;
            // 设置P2节点
            p2->next=p1;
            // 如果第一个节点是头的下一跳，置空
            // 防止形成环，只出现在第一个和第二个节点之间。要把循环去掉，否则打印时会出现死循环
            if(p1==head) {
                p1->next=NULL;
            }
            p1=p2;
            p2=p3;
        }
    return p1;
    }              //head变成新头节点返回 
    else return head;
}

二、插入法

不会出现上面的环，并且head和p1都不会改变，只需要改变p2,p3即可。

/**
 * 插值法逆序[有头部]
 * @param head
 */
void reverse2(pNode &head){
    // 至少两个节点才能逆序
    if(head->next!=NULL&&head->next->next!=NULL){
        pNode p1=head->next,p2=head->next->next,p3=NULL;
        while(p2){
            // 获取循环P3+i节点
            p3=p2->next;                  //插入顺序从后往前
            // P1链接去新的P3+i
            p1->next=p3;
            // P2+i链接去头部
            p2->next=head->next;          //注意用head->next
            // 头部连上P2+i
            head->next=p2;
            // 进入下一个循环
            p2=p3;
        }
    }
    else return;
}

三、递归

采用递归的方式，如果要将当前结点逆序，那么先将它的后继结点都逆序，然后把逆序后的尾结点的next指向当前结点即可，要注意的是递归出口，我们选择链表为空或者只有一个结点的情况为递归出口。

第一次递归调用：

头节点head的下一个节点head->next将是逆序后的新链表的尾节点，也就是说，被摘除的头接点head需要被连接到head->next才能完成整个链表的逆序

第二次递归：

再进行一次递归：

递归终止条件就是链表只剩一个节点时直接返回这个节点的指针。可以看出这个算法的核心其实是在回朔部分，递归的目的是遍历到链表的尾节点，然后通过逐级回朔将节点的next指针翻转过来。

不带头结点

pNode reverse3_no_head(pNode head){
    if(head==NULL||head->next==NULL){
        return head;
    } else {
            pNode newHead = reverse3_no_head(head->next);  //递归部分
            head->next->next = head;         //回溯部分
            head->next = NULL;
            return newHead;
        }
}

带头节点

void reverse3_with_head(pNode &head){
    if (head == NULL){
            return;
        }
    pNode newHead = reverse3_no_head(head->next);   //结合不带头结点的递归
    head->next = newHead;
}

全部代码

#include <iostream>

using namespace std;
typedef struct Node {
    int data;
    struct Node *next;
} Node, *pNode;

/**
 * 初始化链头
 * @param head 外部引用
 */
void initHead(pNode &head) {
    head = new Node;
    head->next = NULL;
}
/**
 * 创建链表
 * @param head
 */
void bulidHead(pNode &head) {
    pNode tail = head;
    tail->next = NULL;
    for (int i = 0; i < 10; i++) {
        pNode p = new Node;
        p->data = i;
        tail->next = p;
        tail = p;
        tail->next = NULL;
    }
}

/**
 * 打印链表
 * @param head
 */
void printHead(pNode head) {
    pNode p = head->next;
    while (p) {
        cout << p->data << " ";
        p = p->next;
    }
}

/**
 * 撤销链表
 * @param head
 */
void destroyHead(pNode &head) {
    pNode p = head;
    while (head) {
        p = head->next;
        delete head;
        head = p;
    }
}


pNode reverse(pNode head) {
    if (head == NULL || head->next == NULL) return head;
    pNode n = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return n;
}

/**
 * 迭代法逆序[有头部]
 * @param head
 */
void reverse1(pNode &head){
    // 至少有除头节点以外两个节点才能逆序
    if(head->next!=NULL&&head->next->next!=NULL){
        // 缓存除了头以外的节点
        pNode p1=head->next,p2=head->next->next,p3=NULL;
        while(p2){
            // 获取循环P3+i节点
            p3=p2->next;
            // 设置二节点下一跳为前一个节点
            p2->next=p1;
            // 如果第一个节点是头的下一跳，置空
            // 防止形成环，只出现在第一个和第二个节点之间。要把循环去掉，否则打印时会出现死循环
            if(p1==head->next) {
                p1->next=NULL;
            }
            // 左移
            p1=p2;
            p2=p3;
        }
        //head变成新头节点返回
        head->next=p1;
    }
    else return;
}

/**
 * 插值法逆序[有头部]
 * @param head
 */
void reverse2(pNode &head){
    // 至少两个节点才能逆序
    if(head->next!=NULL&&head->next->next!=NULL){
        pNode p1=head->next,p2=head->next->next,p3=NULL;
        while(p2){
            // 获取循环P3+i节点
            p3=p2->next;                  //插入顺序从后往前
            // P1链接去新的P3+i
            p1->next=p3;
            // P2+i链接去头部
            p2->next=head->next;          //注意用head->next
            // 头部连上P2+i
            head->next=p2;
            // 进入下一个循环
            p2=p3;
        }
    }
    else return;
}

/**
 * 递归逆序[无头部]
 * @param head
 * @return
 */
pNode reverse3_no_head(pNode head) {
    if (head == NULL || head->next == NULL) {
        return head;
    } else {
        pNode newHead = reverse3_no_head(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
    }
}

/**
 * 递归逆序[有头部]
 * @param head
 */
void reverse3_with_head(pNode &head) {
    if (head == NULL) {
        return;
    }
    pNode newHead = reverse3_no_head(head->next);
    head->next = newHead;
}

int main() {
    pNode head = NULL;
    initHead(head);
    bulidHead(head);
    printHead(head);
    cout << endl;
    reverse3_with_head(head);
    printHead(head);
    destroyHead(head);
    return 0;
}

关于Zeno Chen

本人涉及的领域较多，杂而不精 程序设计语言: Perl, Java, PHP, Python; 数据库系统: MySQL,Oracle; 偶尔做做电路板的开发，主攻STM32单片机
此条目发表在C/C++分类目录。将固定链接加入收藏夹。