`
frank-liu
  • 浏览: 1680883 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

反转单链表

 
阅读更多

简介

    这是一个相对比较简单直接的问题。假设我们有这么一个单链表,需要将它反转过来。对它分析的过程结合图的形式来看会比较清晰直观一点。

 

分析

    我们要通过遍历的方式来反转链表,那么就需要考虑每次反转的时候需要将当前元素指向它原来的前面一个元素。因此,我们需要有一个变量来保存要反转元素的前面一个元素。另外,我们在遍历的时候,要调整当前元素时,为了能够找到后面的结点,需要用到一个额外的变量来指向调整元素,同时调整完之后保证指向前面的元素转而指向当前。

    这么个过程显得比较晦涩,用图表的方式来看就很直观了。

    假定我们有一个链表,并且声明了两个变量,prev, temp:

 

 

     在开始的时候,temp = null, prev = null。接着,我们将temp = head; 这样temp就指向head当前的位置,同时将head指向它下一个位置,也就是head = head.next; 由于我们假定prev表示当前元素的前一个元素。开始的时候prev = null, 我们当前的这个元素是temp所指向的。我们再将temp.next = prev;这样就将第一个元素给反转过来了。如下图所示:

 

 

     当然,为了紧跟head这个元素。prev本身必须是head的前一个,所以在前面一步的设置完成后,我们需要将prev跟进。正好temp指的是当前的,那么就需要将prev = temp。这样结果就如下图了:

 

    这样,经过前面几个步骤,我们就已经将第一个元素给反转过来了。后面的过程也类似。假设我们要接着反转第二个元素,那么它的过程如下图:

 

 

     这一步骤相当于执行了这么两句:temp = head; head = head.next;

     这一步则是将temp所指向的元素反转,也就是:prev = temp.next;

     有了前一步的过程,这一步就是相当于要将prev跟上,也就是:prev = temp;

    ok, 有了前面的这两轮走下来,我们发现他们所要调整的步骤主要如下:

    1. temp = head; // 指定当前要调整的点。

    2. head = head.next; // 走向下一个要被调整的点

    3. temp.next = prev; // 将当前的点反转

    4. prev = temp; // 表示当前调整结点的前一个结点跟进

    以上的4个步骤构成了一个循环。循环的终止条件是head == null;这样,我们很快可以得到一个单链表反转的方法:

public static Node reverse(Node head)
{
    Node prev = null;
    Node temp = null;
    while(head != null)
    {
        temp = head;
        head = head.next;
        temp.next = prev;
        prev = temp;
    }
    return temp;
}

总结

    单链表反转的过程并不复杂,只是它的过程如果不仔细整理清楚的话容易出错。用画图描述每个小步骤的方法可以帮助理请思路。 

 

补充

    反转单链表的方法当然不止前面那一种,还有几种比较常见的,比如说借助堆栈的方式来实现;新建一个链表,每次在表头插入原有链表的元素以及一种递归的方式。这里就对这几种方式也增加一个辅助的分析。

辅助堆栈

    整个的过程其实还是比较简单,我们从原有链表头开始,遍历所有的元素,遍历中将每次碰到元素都压入堆栈。结束这个过程后再将堆栈的元素依次弹出来,重新构造一个新的链表。一种大致的实现代码如下:

Node reverse(LinkedList list)
{
    Node node = list.head;
    Stack<Node> stack = new Stack<Node>();
    while(node != null)  // 所有元素入栈
    {
        stack.push(node);
    }

    Node newHead, item;
    if(!stack.empty())
    {
        newHead = stack.pop();
        item = newHead;
     }
    // 再将元素出栈重新构造
    while(!stack.empty())
    {
        Node temp = stack.pop();
        item.next = temp;
        item = item.next;
    }

    return newHead;
}

 

新建链表

    新建链表的方式也比较简单,首先建立一个空的链表,然后将在遍历原来链表元素的时候每次将元素从新链表的头元素后面插入。

Node reverse(LinkedList list)
{
    LinkedList newList = new LinkedList();
    Node item = list.head;
    while(item != null)
    {
        item.next = newList.head.next
        newList.head.next = item;
    }

    return item.head;
}

    这里假定已经定义好了LinkedList和Node的数据类型。

 

递归

    除了前面采用的方法,实际上还有一种办法,就是递归的方式。在这里,我们假定定义了一个全局访问的成员head,可以作为返回的链表头。递归的方法考虑的一个关系如下:如果我们当前的元素不是到了链表的尾部,则递归到下一层。这样一直到原来链表的末尾,我们将当前元素的引用设置为全局head。在每一层递归返回的时候,将它设置为后面元素的next引用。一种参考代码的实现如下:

Node head = null;

void reverse(Node head)
{
    if(node.next != null)
    {
        reverse(node.next);
        node.next.next = node;
    }
    else
    {
        head = node;
        return;
    }
}

    总的来说,实现一个链表的反转其实方法还是挺多的。各种方法的思路确实都有其特点。

参考资料

Introduction to algorithms

  • 大小: 10.2 KB
  • 大小: 10.8 KB
  • 大小: 11.1 KB
  • 大小: 11.1 KB
  • 大小: 11.3 KB
  • 大小: 11.3 KB
分享到:
评论

相关推荐

    两种方法反转单链表

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

    Python3实现的反转单链表算法示例

    反转单链表是常见的链表操作之一,它将链表中的顺序颠倒,例如原本的1-&gt;2-&gt;3-&gt;4反转后变为4-&gt;3-&gt;2-&gt;1。本文将深入探讨如何使用Python3实现这个操作,包括迭代和递归两种方法。 ### 方案一:迭代 迭代方法是通过...

    单链表的就地反转

    单链表的就地反转是指在不使用额外的存储空间的情况下,反转单链表的节点顺序。该操作对链表的结构进行了重新组织,使得链表的节点顺序被反转。 在该实验报告中,我们将学习如何使用C语言来实现单链表的就地反转。...

    单链表反转

    单链表反转是面试时经常会遇到的问题,之前只是在数据结构里用伪代码实现过单链表反转。为落实亲手编写每一个程序的目标,在这里用java实现反转。方法有很多,这里只写最优的。时间复杂度O(n),空间复杂度O(1)。也...

    C++ 单链表反转 C++ 单链表反转

    单链表反转是一个常见的操作,它将链表中的节点顺序颠倒。给定的代码实现了一个函数`Reverse`来完成这个任务。下面我们将详细讨论这个反转过程。 首先,我们需要检查输入的链表头是否为空。如果为空,则无需反转,...

    C用类实现单链表操作

    - `nodesreverse(void)`:反转单链表。 3. **私有数据成员**: - `struct list`:定义单链表节点的结构。 - `int index`:节点存储的数据。 - `list *next`:指向下一个节点的指针。 - `list *head, *end`:...

    LeetCode每日一题高频面试算法题目1

    本资源是一个 LeetCode 高频面试算法题目集合,包括队列实现栈、反转单链表、合并两个排序数组等多个算法题目。 1. 队列实现栈: 在该题目中,我们使用了两个队列来实现栈的功能。队列是 First-In-First-Out(FIFO...

    单链表常考算法及代码

    6. **反转单链表 (reverse_list)** 7. **寻找中间节点 (searchmid)** #### 三、具体实现 ##### 1. 创建单链表 ```cpp node* creat() { int x, cycle = 1; node* head, * p, * s; head = NULL; s = (node*)...

    单链表反转python实现代码示例

    1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur-&gt;next指向pre即可。 代码: class ListNode: def __init__(self,x): self.val=x; self.next=None; def nonrecurse(head):...

    单链表基本操作-面试必备

    反转单链表是指改变链表节点之间的连接关系,使得原链表的尾部变成头部,头部变成尾部。`reverse_loop()`函数利用迭代的方式实现了链表的反转。 **代码示例:** ```c++ void reverse_loop(PNODE &list) { if (!...

    单链表的基本操作的实现.rar

    反转单链表是一个常见的算法问题,可以通过迭代或递归方式实现。迭代法需要三个指针:当前节点、前一个节点和临时前一个节点。每次遍历,都会将当前节点的指针指向前一个节点,然后更新前一个节点为当前节点,最后...

    数据结构---线性表之单链表(C语言)

    例如,反转单链表可以使用迭代或递归方法,查找特定值的节点则需要遍历链表。 五、注意事项 在处理链表时,需要注意内存管理。创建新节点时要使用`malloc`分配内存,不再需要时记得用`free`释放,以避免内存泄漏。...

    单链表基本操作【超全】

    6. **反转单链表** 反转链表是一个常见的操作,它将链表的顺序倒置。这可以通过迭代或递归实现,关键在于改变节点间的指向关系,使得每个节点的指针都指向其前一个节点。 7. **合并两个有序链表** 如果有两个已排序...

    单链表插入

    ### 反转单链表 `stud*Reverse(stud*person)` 函数可以将整个链表中的节点顺序反转。这是通过维护三个指针(当前节点、前一个节点和后一个节点)来实现的。每次迭代都会将当前节点的 `next` 指针指向它的前一个节点...

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

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

    算法大全-面试题-数据结构.docx

    算法2使用递归的方式来反转单链表,但需要考虑特殊情况,如无元素或只有一个元素的单链表。 2. 找出单链表的倒数第4个元素 可以使用双指针法来解决这个问题。假设链表的长度为n,那么可以使用两个指针,一个指针...

    单链表的插入、删除、逆转等实现

    3. **`Reverse()`**:反转单链表。 ```cpp template void Chain&lt;T&gt;::Reverse() { ChainNode*current=first-&gt;link,*previous=0; while(current) { ChainNode*r=previous; previous=current; current=...

Global site tag (gtag.js) - Google Analytics