`
jefferent
  • 浏览: 79921 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

单链表反转

阅读更多

这道题目有两种算法,既然是要反转,那么肯定是要破坏原有的数据结构的: 算法:我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext:

public static Link ReverseLink1(Link head) 
{ 
	Link curr = head.Next; 
	Link next = null; 
	Link nextnext = null; //if no elements or only one element exists 
	if (curr == null || curr.Next == null) { 
		return head; 
	} //if more than one element 
	while (curr.Next != null) { 
		next = curr.Next; //1 
		nextnext = next.Next; //2 
		next.Next = head.Next; //3 
		head.Next = next; //4 
		curr.Next = nextnext; //5 
	} 
	return head; 
}

 

    算法的核心是while循环中的5句话 我们发现,curr始终指向第1个元素。 此外,出于编程的严谨性,还要考虑2种极特殊的情况:没有元素的单链表,以及只有一个元素的单链表,都是不需要反转的。

 

C语言实现

 

非递归方式:这是一般的方法,总之就是用了几个临时变量,然后遍历整个链表,将当前节点的下一节点置为前节点

void reverse(node*& head)
    {
        if ( (head == 0) || (head->next == 0) ) return;// 边界检测
        node* pNext = 0;
        node* pPrev = head;// 保存链表头节点
        node* pCur = head->next;// 获取当前节点
        while (pCur != 0)
        {
            pNext = pCur->next;// 将下一个节点保存下来
            pCur->next = pPrev;// 将当前节点的下一节点置为前节点
            pPrev = pCur;// 将当前节点保存为前一节点
            pCur = pNext;// 将当前节点置为下一节点
       }
        head->next = 0; //将旧head节点设置为尾部节点
        head = pPre;  //设置当前遍历的最后一个节点为新的头节点
    }

  

递归方式:这个方法是采用了递归算法,也就是在反转当前节点之前先反转其后继节点,利用函数的调用堆栈构建了一个临时链表。采用此算法需要注意的是,头结点必须要传入的是引用,因为在递归跳出的时候要切断链表,否则链表将会形成一个回环。

 

    node* reverse( node* pNode, node*& head)
    {
        if ( (pNode == 0) || (pNode->next == 0) ) // 递归跳出条件
        {
            head = pNode; // 将链表切断,否则会形成回环
            return pNode;
        }

        node* temp = reserve(pNode->next, head);// 递归
        temp->next = pNode;// 将下一节点置为当前节点,既前置节点
        return pNode;// 返回当前节点
    }

 

 

分享到:
评论

相关推荐

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

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

    单链表反转python实现代码

    单链表反转的python实现,简洁详细易于理解,附带注释易于分析

    C语言O(1)空间复杂度实现单链表反转

    用C语言O(1)空间复杂度实现单链表反转,C语言数据结构的作业,有需要的尽管拿去用吧,赚点小分,无聊腻了

    C语言实现单链表反转

    主要介绍了C语言实现单链表反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    单链表反转 链表相交

    实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....

    Java算法篇-单链表反转详解.pptx.pptx

    单链表的定义 单链表是一种线性数据结构,它包含一系列的节点,每个节点都含有一个值和指向下一个节点的引用。 单链表的特性 单链表具有动态性,可以灵活地插入和删除元素,但访问元素时需要从头节点开始顺序查找。 ...

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

    主要介绍了单链表反转python实现,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下

    链表反转的C语言程序

    定义一个5个节点的单链表,然后通过指针的移动调换链表节点的顺序,从而实现链表的反转

    单链表的反转,冒泡和选择排序

    对数据结构不是很熟,用c++实现的单链表反转,冒泡和选择排序,有问题的话请批评指正

    链表创建,单链表反转,逆序打印等等

    关于单链表以及搜集的一些面试题关于单链表的面试题 链表是以节点的方式来存储 每个节点都包含一个data域和next域,data域用来存放数据,next域用来指向下一个节点 链表的各个节点不一定是连续存储的 先来看普通...

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

    单链表的反转是常见的面试题目,下面这篇文章主要给大家介绍了关于单链表实现反转的3种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧

    单链表的基本操作面试题

    单链表的基本操作:建立,查找,插入,删除等。 检查单链表是不是有环。 寻找单链表的中间元素。 单链表反转。

    python如何实现单链表的反转

    主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

    反转单链表

    让一个单链表反转,就是头当做尾,尾做头,各个结点的指向反向

    单链表的就地反转

    单链表的就地反转

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

    1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级...

    单链表的反转(原地反转法 && 新建链表插入法)

    c++ 实现单链表的反转(原地反转法 && 新建链表插入法)

Global site tag (gtag.js) - Google Analytics