java 反转链表
知乎上看到的一个问题。虽然比较简单,还是把解题思路记录一下。
参考:https://www.zhihu.com/question/27090581
一、问题
https://discuss.leetcode.com/category/214/reverse-linked-list
Reverse a singly linked list.
1 |
1 -> 2 -> 3 -> 4 -> 5 |
to
1 |
5 -> 4 -> 3 -> 2 -> 1 |
二、解题思路
这题没有强调一定要在原链表内操作。我们完全可以把链表中的所有元素取出来,放在数组(或者其他容器)中,再自行构造一条新的链表,一样能达到题目效果。
问题是,这种做法需要借助外部空间,需要遍历一次链表,再遍历一次数组容器,效率不高,需要另外的解法。
(1)直观的解法
我一开始想到的是比较直观的解法:
获取头结点后,首先记录头结点的下一个节点(作为下个操作的节点),然后把头结点的指向改成头结点的上一个节点(反转当前节点的指向),之后把当前操作对象记录下来(用于给下个节点的指向留下记录),最后把头结点换成下一个操作的节点(重复此过程)。
ReverseLinkedList.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
public static Node reverse1(Node head) { Node pre = null; while (head != null) { Node next = head.next; // 记录下个操作节点 head.next = pre; // 反转当前节点的指向 pre = head; // 记录当前节点,给下个操作节点的指向做准备 head = next; // 更新当前节点为下个节点,循环此过程 } return pre; } |
(2)递归解法
参考leetcode上的discuss。
我尝试理解了一下这个算法:
首先获取链表的头结点,记录头结点的下一个节点(作为下个操作的节点),然后立刻递归反转下一个节点。具体的反转操作为:让下一个节点指向当前节点,然后把当前节点的指向置为空(避免出现死循环,同时保证最后一个节点指向为null)。
ReverseLinkedList.java
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public static Node reverse2(Node head) { if (head == null || head.next == null) return head; Node nextNode = head.next; Node newHead = reverse2(nextNode); nextNode.next = head; head.next = null; return newHead; } |
个人认为这种解法思路清奇,不太直观,但是依然能解决问题。
(3)比较相似的解题思路
思路和(1)没有什么区别。
ReverseLinkedList.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public Node reverse3(Node head) { if (head == null || head.next == null) return head; Node pre = null; Node curr = head; while (curr != null) { Node next = curr.next; curr.next = pre; pre = curr; curr = next; } return pre; } |
三、总结
此题算是比较简单,稍微想一想就能得到(1)的解法。参考别人的解题思路反而比较难以理解…