算法：翻转链表 Reverse Linked List 三种方法实现，迭代解决人类思维，递归解决机器思维 reverse node

题目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL 

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

自定义链表

为了打印链表信息，笔者组装了链表

package common; public class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val = val; } static public ListNode listNodeWithIntArray(int[] input) { ListNode head = new ListNode(0); ListNode node = head; for (int i: input) { ListNode newNode = new ListNode(i); node.next = newNode; node = node.next; } return head.next; } @Override public String toString() { StringBuilder sb = new StringBuilder(); ListNode node = this; while (node != null) { sb.append(node.val).append("-->"); node = node.next; } return sb.append("Null").toString(); } @Override public boolean equals(Object obj) { if (this == obj) { return true; } return false; } } 

1. 迭代解决（顺序思维，人类思维）

假设我们有链表1 → 2 → 3 → Ø，我们想将其更改为Ø ← 1 ← 2 ← 3。

在遍历列表时，更改当前节点的下一个指针以指向其上一个元素。由于一个节点没有对其先前节点的引用，因此必须预先存储其先前元素。在更改引用之前，您还需要另一个指针来存储下一个节点。不要忘了最后返回新的主要参考！

复杂度分析

时间复杂度： 上）O （n ）。假使，假设ññ 是列表的长度，时间复杂度是 上）O （n ）。

空间复杂度： O（1）O （1 ）。

package linkedlist; import common.ListNode; // https://leetcode.com/problems/reverse-linked-list/ public class ReverseLinkedList { public ListNode reverseList(ListNode head) { // check edge if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; slow.next = null; ListNode temp; while (fast != null) { temp = fast.next; fast.next = slow; slow = fast; fast = temp; } return slow; } } 

2. 递归解决（逆向思维，机器思维）

就是把上面的while 循环部分，改为递归实现.
递归注意先写退出条件：if (fast == null) return slow;.

package linkedlist; import common.ListNode; // https://leetcode.com/problems/reverse-linked-list/ public class ReverseLinkedList { public ListNode reverseListWithRecursive(ListNode head) { // check edge if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; slow.next = null; return reverseList(fast, slow); } private ListNode reverseList(ListNode fast, ListNode slow) { if (fast == null) { return slow; } ListNode temp = fast.next; fast.next = slow; slow = fast; fast = temp; return reverseList(fast, slow); } } 

3. 递归实现 （不需要辅助方法）

递归版本有些棘手，关键是向后工作。假设列表的其余部分已经被撤消，那么我该如何撤回前面的部分？假设列表为：n1 → … → nk-1 → nk → nk+1 → … → nm → Ø

假设从节点n k + 1到n m已反转，并且您在节点n k处。

n1 → … → nk-1 → nk → nk+1 ← … ← nm 

我们希望n k + 1的下一个节点指向n k。

所以，

nk.next.next = nk; 

要非常小心，n 1的下一个必须指向Ø。如果您忘记了这一点，则您的链表中会有一个循环。如果您使用大小为2的链表测试代码，则可能会捕获此错误。

复杂度分析

时间复杂度： 上）O （n ）。假使，假设ññ 是列表的长度，时间复杂度是 上）O （n ）。

空间复杂度： 上）O （n ）。由于递归，额外的空间来自隐式堆栈空间。递归可以上升到ññ 水平深。

package linkedlist; import common.ListNode; // https://leetcode.com/problems/reverse-linked-list/ public class ReverseLinkedList { public ListNode reverseListWithRecursiveClean(ListNode head) { // check edge if (head == null || head.next == null) { return head; } ListNode result = reverseListWithRecursiveClean(head.next); head.next.next = head; head.next = null; return result; } public static void main(String[] args) { ReverseLinkedList obj = new ReverseLinkedList(); int[] input = {1, 2, 3, 4, 5}; ListNode head = ListNode.listNodeWithIntArray(input); System.out.println("init ListNode"); System.out.println(head.toString()); //ListNode result = obj.reverseList(head); //ListNode result = obj.reverseListWithRecursive(head); ListNode result = obj.reverseListWithRecursiveClean(head); System.out.println("result ListNode"); System.out.println(result.toString()); } } 

4. 最终结果打印输出

package linkedlist; import common.ListNode; // https://leetcode.com/problems/reverse-linked-list/ public class ReverseLinkedList { public static void main(String[] args) { ReverseLinkedList obj = new ReverseLinkedList(); int[] input = {1, 2, 3, 4, 5}; ListNode head = ListNode.listNodeWithIntArray(input); System.out.println("init ListNode"); System.out.println(head.toString()); //ListNode result = obj.reverseList(head); //ListNode result = obj.reverseListWithRecursive(head); ListNode result = obj.reverseListWithRecursiveClean(head); System.out.println("result ListNode"); System.out.println(result.toString()); } } 

控制台输出

init ListNode 1-->2-->3-->4-->5-->Null result ListNode 5-->4-->3-->2-->1-->Null