这道题目有两种算法,既然是要反转,那么肯定是要破坏原有的数据结构的: 算法:我们需要额外的两个变量来存储当前节点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++ 单链表反转
单链表反转的python实现,简洁详细易于理解,附带注释易于分析
用C语言O(1)空间复杂度实现单链表反转,C语言数据结构的作业,有需要的尽管拿去用吧,赚点小分,无聊腻了
主要介绍了C语言实现单链表反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....
单链表的定义 单链表是一种线性数据结构,它包含一系列的节点,每个节点都含有一个值和指向下一个节点的引用。 单链表的特性 单链表具有动态性,可以灵活地插入和删除元素,但访问元素时需要从头节点开始顺序查找。 ...
主要介绍了单链表反转python实现,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
定义一个5个节点的单链表,然后通过指针的移动调换链表节点的顺序,从而实现链表的反转
对数据结构不是很熟,用c++实现的单链表反转,冒泡和选择排序,有问题的话请批评指正
关于单链表以及搜集的一些面试题关于单链表的面试题 链表是以节点的方式来存储 每个节点都包含一个data域和next域,data域用来存放数据,next域用来指向下一个节点 链表的各个节点不一定是连续存储的 先来看普通...
单链表的反转是常见的面试题目,下面这篇文章主要给大家介绍了关于单链表实现反转的3种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面来一起学习学习吧
单链表的基本操作:建立,查找,插入,删除等。 检查单链表是不是有环。 寻找单链表的中间元素。 单链表反转。
主要介绍了python如何实现单链表的反转,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
让一个单链表反转,就是头当做尾,尾做头,各个结点的指向反向
单链表的就地反转
1.单链表反转 2.找出单链表的倒数第4个元素 3.找出单链表的中间元素 4.删除无头单链表的一个节点 5.两个不交叉的有序链表的合并 6.有个二级单链表,其中每个元素都含有一个指向一个单链表的指针。写程序把这个二级...
c++ 实现单链表的反转(原地反转法 && 新建链表插入法)