美文网首页Android开发经验谈Android技术知识Android开发
单向链表反转算法

单向链表反转算法

作者: Joker_Wan | 来源:发表于2020-10-16 18:23 被阅读0次

常用的4种：

  1. 迭代反转法
  2. 递归反转法
  3. 头插法
  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;
}

相关文章

  • 数据结构 - 单向链表及相关算法

    单向链表 链表常见算法 链表反转

  • 单向链表反转算法

    常用的4种： 迭代反转法 递归反转法 头插法 就地逆置法 1 迭代反转法 从当前链表的首元节点开始，一直遍历至链表...

  • reverse linked list

    反转单向链表 demo 运行效果

  • 数据结构专题：1.单向链表反转与排序

    有如下单向链表 1.单向链表反转，递归 递归的方式其实是从尾节点开始进行指针反转，最终递归反转到头节点 2.单向链...

  • 单向链表算法

    单向链表 反转单向链表 单链表查找倒数第k个节点 单链表递归倒序打印 单链表排序 单链表删除重复节点

  • 数据结构-链表

    相关掌握点 单向链表 双向链表 反转单向链表 判断链表是否含有环 链表构建 链表是一种线性结构，是通过指针引用节点...

  • 单向链表-链表反转

    最近在并行复习数据结构与算法的知识，为了加强掌握，就把做题思路用画图的方式记录下来。今天是第一篇，常见的问题：链表...

  • 链表 - 单向链表反转

    反转一个单链表。输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 图解...

  • 链表常见问题

    反转单向链表思路使用一个临时节点当做缓冲节点,通过绕圈完成反转 反转部分链表题:给定一个链表,及反转的范围,完成反...

  • 单向链表反转

    https://blog.csdn.net/blioo/article/details/62050967

网友评论

    本文标题：单向链表反转算法

    本文链接：https://www.haomeiwen.com/subject/djctmktx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    Android开发经验谈

    Android技术知识

    Android开发

    Android开发

    关于我们|服务条款|联系我们|单向链表反转算法|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！