通过迭代来实现链表的反转,我们需要三个变量:
那我们怎么通过这三个变量来实现链表的反转呢?让我们先看一下实现步骤:
**注意:**好,我们的链表当next==null时,链表也正确的完成了反转。
那我们前面所疑惑的问题:为什么当我们递归之前要进行一次反转也就不言而喻了。因为,如果我们不在递归前进行一次反转的话,最后一次我们会少反转一个节点(当递归反转结束后,会丢失原始链表中的尾节点)。
通过递归来实现链表的反转,我们只需要将一个待反转的链表看作两部分:
一个未被反转的节点:
第一次递归中,这个节点就是原始链表的头结点【head】。
一个已经完成反转的链表:
第一次递归中,这个链表是除了原始链表的头结点,其余节点所完成反转后的链表【这个当前链表的尾节点是 head.next】
同样,链表反转的过程,我们通过画图来说明:
怎么样?递归反转我们也学会了,是不是也并没有多么复杂。我们只是通过最终的结果来反推子结果,再通过子结果再继续反推,直到反推到已排序的节点只有一个时,我们也就可以一步步得到上一步的结果,最终的实现我们整个链表的反转。
通过头插法来实现链表的反转,与迭代反转一样,也需要三个变量来保留待插节点、待插节点的前一个节点、待插节点的下一个节点。
在画图之前,我们先思考一个问题:头插法实现链表反转他是怎么实现的呢?我们就想象一下,这个带反转的链表它只有两个节点,head和head.next,我们怎么将这个链表来实现反转呢?
是不是只需要先让head插在null上,再让head.next插在head上就实现了反转。
那我们再继续思考,为什么需要三个变量呢?
第一次,我们让head.next=null时,我们需要一个变量a=null吧
我们需要让一个变量b=head吧,此时我们就可以让head.next=null了,但是注意,如果这时直接让head.next=null,那么原始链表中head后的其他节点就全部丢失了
所以,我们还需要一个变量c=head.next吧。
好我们来捋一下顺序
a=null;
b=head;
c=head.next;
b.next=a; // 实现了head.next=null
来,我们继续思考,怎么让head.next.next=head?
一样的,需要一个变量a=head,一个变量b=head.next,那还需要一个变量c=head.next.next?没错需要变量c=head.next.next(对于我们两个节点的链表而言,这个c此时为null)
a=head;
b=head.next;
c=head.next.next; // 这个我们先不确定,可能需要这个变量
b.next=a; // 实现head.next.next=head
我们观察上述两个代码块,思考这是不是可以写一个循环啦?
a=null;
while(循环条件){
b=head;
head=head.next;
b.next=a;
}
我们继续思考循环条件是什么,或者这个循环什么时候退出呢?
是不是当head==null的时候,退出循环?
我们通过画图来进行验证:
好,我们通过画图实现了链表的反转,也可以看到我们上面写的循环是有点问题,那我们做一些改变,并将变量重新命一下名。
...
head // 头结点
...
// newHead就是那个a变量
// temp就是那个b变量
Node newHead=null, temp;
while(head!=null){
temp=head;
head=head.next;
temp.next=newHead;
newHead=temp;
}
package edu.hrbu.test;
/**
* @author 徐登宇
*/
public class TestReverseLink {
// 链表节点的数据结构
private static class Node{
private int data; // 当前节点的值
private Node next; // 当前节点指向的下一个节点
public Node(int data){
this.data=data;
}
}
// 构建链表并返回头结点
private static Node createLink(){
Node head = new Node(1);
Node n1 = new Node(2);
Node n2 = new Node(3);
Node n3 = new Node(4);
Node n4 = new Node(5);
head.next=n1;
n1.next=n2;
n2.next=n3;
n3.next=n4;
return head;
}
// 打印链表
private static void printLink(Node head){
// 如果链表只有一个节点,直接打印该节点的值
if (head.next==null) System.out.println(head.data);
while (head!=null){
System.out.print(head.data+" -> ");
head=head.next;
}
}
/**
* 通过迭代来实现链表反转
*
* 需要用到三个变量,
* prev:保存当前节点的前一个节点
* curr:保存当前节点
* next:保存当前节点的下一个节点
*
* 具体怎么实现链表反转?
*
*
*
* @param head 原始链表头结点
* @return 链表反转后的新的头结点
*/
private static Node reverseWithIterate(Node head){
// 如果链表没有节点或只有一个节点,直接返回
if (head==null||head.next==null) return head;
// 需要三个变量保存我们当前走到的节点以及它的前一个节点和后一个节点
Node prev=null; // 当前节点的前一个节点,反转被指向的节点
Node curr=head; // 当前节点
Node next=head.next; // 当前节点的下一个节点,用来判断链表是否走到头,并用来保留原始链表
// 在循环反转之前,我们先进行一次反转
curr.next=prev;
// 进行循环反转
while (next!=null){
prev=curr;
curr=next;
next=next.next;
// 反转
curr.next=prev;
}
return curr;
}
/**
* 通过递归方法来实现链表反转
*
* 需要一个变量来存储反转后的链表的头结点【新的头结点】
*
* 怎么通过递归实现链表反转的呢?
* 一、将未反转的链表看作两部分:1. 原始的头结点;2. 已经实现反转的新链表【我们要接收这个新链表的头结点,最后将最终的新链表的头结点返回出去】
* 二、让原始链表头结点的下一个节点执行这个原始链表的头结点,并将原始的头结点的next置为空,这样原始链表的头结点就成为了反转后的链表的尾节点,实现了最终的链表的反转。
*
* @param head 原始链表头结点
* @return 链表反转后的新的头结点
*/
private static Node reverseWithRecursive(Node head){
// 递归结束条件:只有一个节点(或者头结点为空,直接不进行递归直接返回)
if (head==null||head.next==null) return head;
// 怎么通过递归实现链表反转的?
// 将原始未反转的链表看作两部分:一个原始链表的头结点,一个已经完成反转的链表。
// 那么,只需要将已经完成反转的链表的尾节点,也就是原始头节点原始指向的下一个节点的next指向原始的头结点,并将原始的头结点的next置空,让原始头结点变为反转后的链表的尾节点,就完成了链表的反转。
// 我们需要一个变量,来接收反转后的链表的头结点,最后将这个反转后的链表的头结点返回就可以了
Node newHead=reverseWithRecursive(head.next);
// 让head的下一个节点反过来指向head
head.next.next=head;
// 将head的next置空
head.next=null;
return newHead;
}
/**
* 通过头插法来实现链表反转
*
* 需要三个变量:
* 1. 作为每次反转时被指向的节点,最后被作为完成反转的链表的头结点返回;
* 2. 作为头插时被插入的头结点
* 3. 作为保存后续节点的作用,并起到判断是否走到链表最后的作用【可以用原始链表的头结点实现这些个作用:每次循环head=head.next就可以】
*
*
* @param head 原始链表头结点
* @return 链表反转后的新的头结点
*/
private static Node reverseWithHeadInsert(Node head){
// 当链表只有一个节点,或者没有节点时,直接返回
if (head==null||head.next==null) return head;
// 头插法实现链表反转,也需要三个变量
// 1. 作为反转后的新的头结点,每次头插最后指向新插上的头结点
// 2. 作为临时节点,实现头插的作用,作为临时的头结点
// 3. 【我们将原始链表的头结点作为这个变量就可以】作为是否走到链表最后的条件,以及实现保存原始链表的节点的作用
Node newHead=null,temp;
while (head!=null){
temp=head;
head=head.next;
temp.next=newHead;
newHead=temp;
}
return newHead;
}
public static void main(String[] args) {
Node head = createLink();
System.out.println("反转前:");
printLink(head);
System.out.println("\n反转后:");
// head=reverseWithIterate(head);
// head=reverseWithRecursive(head);
head=reverseWithHeadInsert(head);
printLink(head);
}
}
文章浏览阅读95次。除了上面的 errors.New 用法之外,我们还可以实现 error 接口自定义一个 Error() 方法,来返回自定义的错误信息。return fmt . Sprintf("出现错误:%.0f 为负数" , e . Num) } func Sqrt(f float64)(float64 , error) {= nil {_go intohex报错
文章浏览阅读2.5k次,点赞5次,收藏14次。线程互斥是指在多线程并发执行时,为避免多个线程访问共享资源时发生冲突而采取的一种机制。本篇文章我们就这个问题来了解一下什么叫线程互斥,又如何解决线程互斥的问题。这篇文章讲解了线程的互斥和线程的死锁,并给出了线程死锁的解决方法。_qt 互斥锁
文章浏览阅读1.8k次。欧几里得算法能够求出两个数值的最大公约数。此算法的确立虽然已经过去2000多年,但因其实现逻辑简单又明确,所以至今还在沿用。具体内容如下。给出两个任意自然数 m 和 n ,为了便于说明,假设 m 总是大于等于 n 。即使如此假设也不会失去算法的通用性,因为必要时可以将 m 和 n 对调。此时,求 m 和 n 的最大公约数。int gcd(int m, int n){ in..._求n个整数的最大公约数
文章浏览阅读1.7k次。功能一,近日遇到需要给输入的文字换行,并自动换二格的问题,几经周折,终于找到了解决方案先判断软键盘输入的是enter键。在这里 return true的是为了防止输入法自身遇到enter键换行,这样就会导致换二行出现。而除了enter 返回false,就是为了让其它的软键盘功能正常使用,不然删除等键全会失效!另外加一个 action_up是为了防止 这里调用2次这个方法。action_do..._edittext set keycode_enter
文章浏览阅读1.3k次,点赞20次,收藏35次。Linux 常用命令_linux常用命令 csdn
文章浏览阅读3.9k次。/** * clearEmptyValue 清除多维数组里面的空值 * @param array $array * @return array * @author liuml * @DateTime 2018/12/3 11:27 */function array_filter_recursive(array &$arr){ if (empty($arr)) ..._php array_filter 多维数组
文章浏览阅读71次。前言前面已经总结了关键字、运算符与魔法方法的对应关系,下面总结python内置函数对应的魔法方法。魔法方法数学计算abs(args):返回绝对值,调用__abs__;round(args):返回四舍五入的值,调用__round__;math.floor():向下取整,调用__floor__;math.ceil():向上取整,调用__ceil__;math.trunc():求一个值距离0最近的整数,..._ipython魔法方法和语法糖
文章浏览阅读942次,点赞3次,收藏2次。本文探讨如何在 Linux 操纵进程。Linux 主要使用 kill 来操纵进程,即杀掉进程。kill 命令是通过发送特定的信号来操纵命令, 列出所有支持的信号。kill 命令发送的默认信号是 15(SIGTERM),即终止信号。另一个比较重要的是信号 9(SIGKILL),即强制终止信号。一般我们先使用 ps 或 top 找到需要终止的进程的 PID,然后将 PID 跟在 kill 后面即可杀掉进程。如果某些恶意进程杀不掉,可使用 强制杀掉。非必要情况,不要使用 ,因为强制终止进程可能会导致数据丢失或者_kill默认信号值
文章浏览阅读4.8k次。Track相关类概述下图是其继承关系图,继承在AudioBufferProvider之后,各种Track可以作为AudioBufferProvider的一种为AudioMixer提供音频数据缓冲。TrackBase是基类,Track作为普通的音轨类,用于音频播放;OutputTrack用于复制线程,相当于将声音同时输出到两个输出设备中。TrackBase在它的构造函数中,在ashm上为_mthread.promote
文章浏览阅读5.5k次。1.iPhone OS 2.0 苹果在2008年3月6日iPhone SDK Roadmap会上正式介绍了iPhone OS 2.0。这个版本的获得的重要更新可以分成一下4大类:-企业增强-微软Exchange ActiveSync-iPhone SDK-App Store 在2008年6月的WWDC大会上苹果宣布包括MobileMe服务以及其他_不同ios版本元素
文章浏览阅读1.9k次,点赞3次,收藏3次。tabs中使用echarts,除了第一个图表能默认显示外,当tabs切换的时候,第一个之后的可能就显示不了了,如何解决?<template> <div> <el-row> <el-col :span="24"> <el-card> <el-tabs v-model="activeName" type="card" @tab-click="handleClick"> ._在element的tabs里面放echarts
文章浏览阅读5.9w次,点赞73次,收藏282次。这里分享一篇文献中椭圆检测的方法(代码使用方法)。圆的物体,在实际拍摄中由于种种原因可能会变成椭圆,用圆拟合就不够准确。_椭圆检测