`

反转单链表的几种方法

阅读更多

详见: http://blog.yemou.net/article/query/info/tytfjhfascvhzxcyt114

 

反转单链表的几种方法

 

  最近试着做一些笔试面试题,既是为来年找工作做准备,也可以做为数据结构和算法的复习笔记,就陆续发在这里吧,有需要的朋友可以看一下,如果有没考虑周全的地方欢迎指正。

  先来一个最常见的题目:反转单链表。假设单链表的数据结构定义如下:

  

typedef struct LNode
{
    int     data;
    struct LNode    *next;
}LNode, *LinkedList;

  并且这个单链表有一个头指针list指向第一个结点,最后一个结点指向NULL,很容易理解。

  最容易想到的第一种方法就是重新建立一个单链表newList,每次将list中的第一个结点放到newList后面。注释比较详细,所以就不具体说了,直接看代码吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
LinkedList ReverseSinglyLinkedList(LinkedList list)
{
    LinkedList  newList;    //新链表的头结点
    LNode       *tmp;       //指向list的第一个结点,也就是要摘除的结点
 
    //
    //参数为空或者内存分配失败则返回NULL
    //
    if (list == NULL || (newList = (LinkedList)malloc(sizeof(LNode))) == NULL)
    {
        return NULL;
    }
 
    //
    //初始化newList
    //
    newList->data = list->data;
    newList->next = NULL;
 
    //
    //依次将list的第一个结点放到newList的第一个结点位置
    //
    while (list->next != NULL)
    {
        tmp = newList->next;         //保存newList中的后续结点
        newList->next = list->next;       //将list的第一个结点放到newList中
        list->next = list->next->next;     //从list中摘除这个结点
        newList->next->next = tmp;        //恢复newList中后续结点的指针
    }
 
    //
    //原头结点应该释放掉,并返回新头结点的指针
    //
    free(list);
    return newList;
}

  第二种方法是每次都将原第一个结点之后的那个结点放在list后面,下图是原始的单链表。单链表反转示例图片

  为了反转这个单链表,我们先让头结点的next域指向结点2,再让结点1的next域指向结点3,最后将结点2的next域指向结点1,就完成了第一次交换,顺序就变成了Header-结点2-结点1-结点3-结点4-NULL,然后进行相同的交换将结点3移动到结点2的前面,然后再将结点4移动到结点3的前面就完成了反转,思路有了,就该写代码了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LinkedList ReverseSinglyLinkedList(LinkedList list)
{
    LNode   *tmp = NULL;
    LNode   *p = NULL;
 
    if (list == NULL)
    {
        return NULL;
    }
    tmp = list->next;
    while (tmp->next != NULL)
    {
        p = tmp->next;
        tmp->next = p->next;
        p->next = list->next;
        list->next = p;
    }
    return list;
}

  第三种方法跟第二种方法差不多,第二种方法是将后面的结点向前移动到头结点的后面,第三种方法是将前面的结点移动到原来的最后一个结点的后面,思路跟第二种方法差不多,就不贴代码了。

  我只想到这三种方法,如果你还知道其它方法,欢迎留言告诉我,多谢。

分享到:
评论

相关推荐

    两种方法反转单链表

    本文将深入探讨两种方法来反转单链表,这些方法是基于Java编程语言实现的,因此相关知识点包括链表操作、递归以及迭代。 首先,我们需要了解单链表的基本结构。在Java中,一个简单的单链表节点可以定义为: ```...

    单链表实现反转的3种方法示例代码

    单链表的操作是面试中经常会遇到的问题,今天总结一下反转的几种方案: 1 ,两两对换 2, 放入数组,倒置数组 3, 递归实现 代码如下: #include #include typedef struct Node { int data; struct Node *...

    List-LinkedList 单链表就地反转

    单链表是一种常见的线性数据结构,其中每个元素包含一个指向下一个元素的指针。就地反转指的是在不使用额外的数据结构的情况下,改变链表中各节点之间的连接关系,使链表的顺序完全颠倒。 #### 代码解析 ##### ...

    C用类实现单链表操作

    在C语言中使用类来实现单链表的操作是一种非常实用的方法,尤其当需要对链表进行复杂的管理时。本篇将基于提供的`node.h`头文件和`node.cpp`源代码,详细阐述如何通过类的方式在C语言中实现单链表的基本操作,包括...

    单链表常考算法及代码

    以上就是单链表常见的几种面试算法及其实现方法。这些算法不仅在面试中经常被提及,在实际工作中也十分有用。掌握它们不仅能提高你的编程能力,还能加深你对数据结构的理解。希望本文对你有所帮助!

    C#编程的单链表的基本操作

    在单链表中插入节点有几种常见情况: 1. 插入到头部:新节点作为新的头节点,原头节点成为新节点的下一个节点。 2. 插入到尾部:遍历链表找到最后一个节点,将新节点插入其后。 3. 插入到指定位置:需找到目标位置的...

    数据结构试验 单链表的基本操作及应用

    在这个"数据结构试验 单链表的基本操作及应用"中,我们可能会涉及以下几个关键知识点: 1. **链表的创建**:首先,我们需要理解如何初始化一个空链表。这通常通过创建一个头节点来实现,头节点的数据域可能为空,但...

    c代码-反转一个单链表。

    接下来,我们介绍几种反转单链表的方法。 ### 方法一:迭代法 迭代法是最直观且易于理解的方式。我们需要三个指针,分别表示当前节点(curr)、前一个节点(prev)和临时前一个节点(temp)。初始时,prev 指向 ...

    单链表操作详解(一)

    在单链表的操作中,主要有以下几种常见操作: 1. **插入节点**:在单链表中插入节点,首先要找到插入位置的前一个节点,然后创建新节点并更新前后两个节点的指针。例如,要在链表中间插入节点,需要找到目标位置的...

    单链表插入

    同样,这个操作也分为几种情况:删除头节点、删除尾节点和其他位置的节点。删除时需要注意释放被删除节点占用的内存空间,并且正确更新前后节点的指针。 ```c if(1==post) { cur=cur->next; person->next=cur->...

    数据结构 实验2 单链表上的操作

    单链表是数据结构中的一种基础且重要的结构,它在计算机科学中有着广泛的应用。本实验将深入探讨如何在单链表上进行各种操作。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的指针。在本实验中,...

    java第一次作业 单链表逆序

    要实现单链表的逆序,你可以采用以下几种方法: 1. **迭代法**: 这是最直观的方法,使用三个指针`prev`、`current`和`next`。初始化时,`prev`为空,`current`为头节点。遍历链表,每次迭代将`current`的`next`...

    单链表基本操作【超全】

    在单链表中插入节点分为几种情况:在链表开头(头部插入)、在链表末尾(尾部插入)以及在链表中的某个特定位置插入。头部插入只需改变头节点即可,尾部插入需要遍历链表找到最后一个节点并进行插入,而在特定位置...

    单链表源码

    单链表是一种基础的数据结构,它在计算机科学中扮演着重要的角色,特别是在数据存储和算法实现方面。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的引用,最后一个节点的引用通常为null,标志着...

    单链表创建

    创建非循环单链表通常涉及以下几个步骤: - 定义节点结构:一个节点通常包含数据部分和一个指向下一个节点的指针。 - 初始化头节点:创建一个空链表,头节点的指针指向null。 - 插入节点:根据需求在链表的头部或...

    简单单链表(数据结构)

    在学习单链表时,还需要注意以下几点: - **空间复杂度和时间复杂度**:链表的空间复杂度主要取决于链表的长度,因为每个节点都需要额外的指针空间。插入和删除操作通常比数组更快,因为它们不需要移动元素,但查找...

    18级合工大数据结构实验单链表

    在单链表的操作中,有几种常见的基本操作: 1. **创建链表**:初始化一个空链表,通常通过创建一个头节点开始,其后继指针为null。 2. **插入节点**:在链表的特定位置插入新节点,需要找到插入位置的前一个节点,...

    单链表的基本操作(很详细)

    反转单链表是常见的链表操作,可以通过迭代或递归实现。迭代方法通常涉及三个指针:前一个节点、当前节点和下一个节点。递归方法则利用函数自身来处理链表的子问题。 ### 6. 合并两个有序链表 将两个已排序的链表...

    单链表的源码

    单链表是一种基础的数据结构,它在计算机科学中扮演着重要的角色,特别是在数据存储和算法实现方面。单链表由一系列节点组成,每个节点包含数据元素以及指向下一个节点的指针。这种数据结构允许动态地添加、删除和...

Global site tag (gtag.js) - Google Analytics