单向链表反转算法

2020-10-16 本文已影响0人 Joker_Wan

常用的4种：

迭代反转法
递归反转法
头插法
就地逆置法

1 迭代反转法

从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，使其指向前一个节点

1.1 定义 3 个指针并分别命名为 beg、mid、end

遍历链表的过程就等价为：3 个指针每次各向后移动一个节点，直至 mid 指向链表中最后一个节点（此时 end 为 NULL ）。需要注意的是，这 3 个指针每移动之前，都需要做一步操作，即改变 mid 所指节点的指针域，另其指向和 beg 相同。

1.2 先改变 mid 所指节点的指针域指向，另其和 beg 相同，然后再将 3 个指针整体各向后移动一个节点，重复这个操作直到 mid 指向最后一个节点

1.3 此时 mid 已经指向最后一个节点，但还需要最后一次修改 mid 所指节点的指针域指向，使其和 beg 相同

1.4 最后只需改变 head 头指针的指向，另其和 mid 同向，就实现了链表的反转

迭代反转法的整个过程用 c语言代码如下：

typedef struct s_node
{
    int data;
    struct s_node* next;
} Node;

Node* iteration_reverse(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    else {
        Node* beg = NULL;
        Node* mid = head;
        Node* end = head->next;
        //一直遍历
        while (1)
        {
            //修改 mid 所指节点的指针域指向beg
            mid->next = beg;
            //此时判断 end 是否为 NULL，如果成立则退出循环
            if (end == NULL) {
                break;
            }
            //整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

伪代码如下：

        while (1)
        {
            mid->next = beg;
            if (end == NULL) {
                break;
            }
            beg = mid;
            mid = end;
            end = end->next;
        }
        head = mid;

2 递归反转法

递归反转法更适用于反转不带头节点的链表
和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。

递归反转法的 C语言实现如下：

Node* recursive_reverse(Node* head) {
    //递归的出口
    //空链或只有一个结点，直接返回头指针
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    
    //一直递归，找到链表中最后一个节点
    Node *new_head = recursive_reverse(head->next);
    
    //当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
    //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
    
    //每退出一层，都需要改变 head->next 节点指针域的指向为上一个节点head，同时令 head 所指节点的指针域为 NULL。
    head->next->next = head;
    head->next = NULL;
    //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
    return new_head;
}

伪代码如下：

Node* recursive_reverse(Node* head) {
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    
    Node *new_head = recursive_reverse(head->next);

    head->next->next = head;
    head->next = NULL;
        
    return new_head;
}

3 头插法

所谓头插法，是指在原有链表的基础上，依次将位于原链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

头插法 C语言实现

Node* head_reverse(Node* head) {
    Node* new_head = NULL;
    Node* temp = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL)
    {
        temp = head;
        //将 temp 从 head 中摘除
        head = head->next;
        
        //将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

伪代码

    while (head != NULL)
    {
        temp = head;
        head = head->next;
        temp->next = new_head;
        new_head = temp;
    }

4. 就地逆置法

就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。

就地逆置法C语言实现

Node* local_reverse(Node* head) {
    Node* beg = NULL;
    Node* end = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // beg 指向第一个节点，end 指向 beg->next
    beg = head;
    end = head->next;
    while (end != NULL) {
        //将 end 从链表中摘除
        beg->next = end->next;
        //将 end 移动至链表头
        end->next = head;
        // 更新head指向表头
        head = end;
        //调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
        end = beg->next;
    }
    return head;
}

伪代码

    beg = head;
    end = head->next;
    while (end != NULL) {
        beg->next = end->next;
        end->next = head;
        head = end;
        end = beg->next;
    }

本文所有代码和例子

//
//  LinkListAlgorithm.c
//
//  Created by jokerwan on 2020/10/15.
//  Copyright © 2020年 jokerwan. All rights reserved.
//

#include "LinkList.h"

#include <stdio.h>
#include <stdlib.h>

// 就地逆置法
Node* local_reverse(Node* head) {
    Node* beg = NULL;
    Node* end = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // beg 指向第一个节点，end 指向 beg->next
    beg = head;
    end = head->next;
    while (end != NULL) {
        //将 end 从链表中摘除
        beg->next = end->next;
        //将 end 移动至链表头
        end->next = head;
        head = end;
        //调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
        end = beg->next;
    }
    return head;
}

// 头插法 构造一个新链表，依次位于将原有链表头部节点取下，采用头部插入方式插入到新链表中
Node* head_reverse(Node* head)
{
    Node* new_head = NULL;
    Node* temp = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL)
    {
        temp = head;
        //将 temp 从 head 中摘除
        head = head->next;
        
        //将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

//递归反转法
Node* recursive_reverse(Node* head)
{
    //递归的出口
    //空链或只有一个结点，直接返回头指针
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    
    //一直递归，找到链表中最后一个节点
    Node *new_head = recursive_reverse(head->next);
    
    //当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
    //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。
    
    //每退出一层，都需要改变 head->next 节点指针域的指向为上一个节点head，同时令 head 所指节点的指针域为 NULL。
    head->next->next = head;
    head->next = NULL;
    //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
    return new_head;
}

//迭代反转法，head 链表的头指针
Node* iteration_reverse(Node* head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    else
    {
        Node* beg = NULL;
        Node* mid = head;
        Node* end = head->next;
        //一直遍历
        while (1)
        {
            //修改 mid 所指节点的指向
            mid->next = beg;
            //此时判断 end 是否为 NULL，如果成立则退出循环
            if (end == NULL)
            {
                break;
            }
            //整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

//测试四种反转算法
int testReverseLinkList()
{
    //创建链表
    Node* head = create_list_head();
    if(NULL == head)
    {
        printf("create_list_head failed!\n");
        return -1;
    }
    
    //填充数据（添加节点）
    int i;
    for(i=5; i>0; i--)
        add_node_head(head, create_new_node(i));
    
    //打印原来链表数据
    printf("befor ");
    display_list(head);
    
    //反转链表
//    head = iteration_reverse(head);
//    head = recursive_reverse(head);
//    head = head_reverse(head);
    head = local_reverse(head);
    
    
    printf("after ");
    display_list(head);
    
    //释放链表空间
    free_list(head);
    return 0;
}


//创建链表
Node* create_list_head()
{
    Node* head = (Node*)malloc(sizeof(Node));
    if(NULL != head)
    {
        head->data= -1;
        head->next= NULL;
    }
    return head;
}

//创建新节点
Node* create_new_node(int node_data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    if(NULL != new_node)
    {
        new_node->data= node_data;
        new_node->next= NULL;
    }
    return new_node;
}

//打印链表数据
void display_list(Node* head)
{
    if(NULL == head)
        return;
    Node* tmp = head;
    printf("list data:");
    while(NULL != tmp)
    {
        printf("%d  ", tmp->data);
        tmp=tmp->next;
    }
    printf("\n");
}


//释放链表
void free_list(Node* head)
{
    if(NULL == head)
        return;
    Node* p = head;
    while((p = p->next))
    {
        head->next = p->next;
        //printf("free:%d\n", p->data);
        free(p);
        p = head;
    }
    free(head);
}


//头插法
int add_node_head(Node* head, Node* new_node)
{
    if(NULL == head || NULL == new_node)
        return -1;
    new_node->next = head->next;
    head->next = new_node;
    return 0;
}

单向链表反转算法

1 迭代反转法

2 递归反转法

3 头插法

4. 就地逆置法

猜你喜欢

热点阅读