java 反转链表

知乎上看到的一个问题。虽然比较简单,还是把解题思路记录一下。

参考:https://www.zhihu.com/question/27090581

 

一、问题

https://discuss.leetcode.com/category/214/reverse-linked-list

Reverse a singly linked list.

to

二、解题思路

这题没有强调一定要在原链表内操作。我们完全可以把链表中的所有元素取出来,放在数组(或者其他容器)中,再自行构造一条新的链表,一样能达到题目效果。

问题是,这种做法需要借助外部空间,需要遍历一次链表,再遍历一次数组容器,效率不高,需要另外的解法。

(1)直观的解法

我一开始想到的是比较直观的解法:

获取头结点后,首先记录头结点的下一个节点(作为下个操作的节点),然后把头结点的指向改成头结点的上一个节点(反转当前节点的指向),之后把当前操作对象记录下来(用于给下个节点的指向留下记录),最后把头结点换成下一个操作的节点(重复此过程)。

ReverseLinkedList.java

(2)递归解法

参考leetcode上的discuss。

我尝试理解了一下这个算法:

首先获取链表的头结点,记录头结点的下一个节点(作为下个操作的节点),然后立刻递归反转下一个节点。具体的反转操作为:让下一个节点指向当前节点,然后把当前节点的指向置为空(避免出现死循环,同时保证最后一个节点指向为null)。

ReverseLinkedList.java

个人认为这种解法思路清奇,不太直观,但是依然能解决问题。

(3)比较相似的解题思路

思路和(1)没有什么区别。

ReverseLinkedList.java

三、总结

此题算是比较简单,稍微想一想就能得到(1)的解法。参考别人的解题思路反而比较难以理解…

发表评论

电子邮件地址不会被公开。 必填项已用*标注