Java教程

如何反转链表?超详细图解,看这一篇就够了!

本文主要是介绍如何反转链表?超详细图解,看这一篇就够了!,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

有如下链表:

file

要求对链表进行反转,反转后的链表如下:

file

题目解析

反转链表,就是将链表中每一个节点的 next 引用指向其前驱节点。链表默认自带一个引用,这个引用指向了头节点,记为 n1。首先尝试将 n1 的 next 引用进行反转:

file

可以发现,① 的 next 引用指向了空,由于 ① 切断了指向 ② 的引用,导致 n1 无法移动到 ② 和 ③,此时可以再引入一个引用,记为 n2,n2 指向 ②:

file

对 ② 进行反转:

file

这时候 ③ 丢失了,是否可以复用现有的引用来访问到 ③ 呢,答案是不行的。 ② 的前驱节点需要通过 n1 来访问,此时需再引入一个新的引用 n3,来指向 ③:

file

对 ③ 进行反转:

file

这时候三节点链表就完成了反转,题目到这是否就分析结束了呢?再引入一个节点 ④,如图:

file

不难发现,④ 节点又丢失了。再思考,能否复用现有引用,来访问到 ④,光从上图的结果来看,是不行的,一旦一个节点完成了反转,其后继节点就丢失了,除非创建与链表节点数量一致的引用,每一个引用指向其中一个节点,然后按上述方式对每个节点完成反转。这种方式显然不够优雅,那能否在反转下一个节点之前,先将引用后移,再反转呢?

接下来我们尝试边反转,边移动引用。通过上述分析,反转链表至少要 3 个引用,可以得出移动的时机是在反转 ③ 的时候,我们在反转 ③ 之前,先后移引用,保证不丢失 ④:

file

然后反转 ③:

file

我们需要指定一个引用,专门用来反转节点 next 指向。显然指定中间引用 n2 是合适的,n1 指向着 n2 的前驱节点,n3 指向着 n2 的后继节点,这样可以既完成反转,又不会丢失后续的节点。因此,我们在反转 ③ 之后,继续后移引用,使得 n2 指向 ④,完成对 ④ 的反转:

file

这里将移动和反转做了合并,可以看到,现在整个链表已经完成了反转。

代码实现

现在,我们只需将上述的分析结果翻译成代码即可。经过分析可知,反转链表一共需要三个引用,为了清晰直观,依次记为 prev、node、next,node 用于反转节点 next 指针。每当完成一次反转,三个引用便整体向后移动一个节点。代码实现如下:

public static Node reverse(Node node) {
	if (node == null || node.next == null) {
		return node;
	}
	
	Node prev = null;
	Node next = node.next;
	
	//next 指向空时,只需再进行最后一次反转
	while (next != null) {
		
		//反转节点
		node.next = prev;
		
		//引用后移
		prev = node;
		node = next;
		next = next.next;
	
	}

	//反转最后一个节点
	node.next = prev;
	
	//返回反转后的链表头引用
	return node;
}

需要注意的是,当 next 引用指向空时,末尾最后一个节点还未反转,所以在循环外要再反转一次。

另外,这里必须将处理好的 node 引用在方法中返回出去,通过拿方法的返回值来获取反转后的链表。如果仍然使用传入的 node,会发现 node 只剩下一个节点。有如下测试代码:

//定义链表:1 -> 2 -> 3
Node node = new Node(1);
node.next = new Node(2);
node.next.next = new Node(3);

System.out.println("原始链表:");
show(node);

//反转链表
Node rNode = reverse(node);

System.out.println("反转后:");
show(node);
show(rNode);

结果如下:

原始链表:
[Node{num=1, next=2}, Node{num=2, next=3}, Node{num=3, next=}]
反转后:
[Node{num=1, next=}]
[Node{num=3, next=2}, Node{num=2, next=1}, Node{num=1, next=}]

这是因为在 Java 中传递的是值,而不是引用。反转后的图例如下:

file

在传递 node 时,是将 node 保存的内存地址复制了一份,传给了方法参数 node,方法中对 node 的移动,不会影响方法外的 node。

反转链表至此完成,在解决链表相关问题时,要时刻注意不能丢失节点,在修改节点 next 或者 prev 指针时,都要保证仍能访问到其他节点,如果发现无法复用现有引用,可以尝试新增引用。保证了这一点之后,剩下的就是按题目要求实现即可。

这篇关于如何反转链表?超详细图解,看这一篇就够了!的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!