算法:ReverseLinkedList

说明

算法&＃xff1a;Minimum Path Sum
LeetCode地址&＃xff1a;https://leetcode.com/problems/reverse-linked-list/

题目&＃xff1a;
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?


解题思路

链表反转&＃xff0c;实现方式有顺序遍历&＃xff0c;还有递归。注意启动头脑系统二进行慢思考验证。

代码 – ListNode

改良后的ListNode可以接受整型数组为参数&＃xff0c;构建一个链表。
toString() 打印链表格式数据:

1-->2-->3-->4-->5-->Null


ListNode

public class ListNode {public int val;public ListNode next;public ListNode(int x) {val &＃61; x;}static public ListNode listNodeWithIntArray(int[] input) {ListNode head &＃61; new ListNode(0);ListNode node &＃61; head;for (int i: input) {ListNode newNode &＃61; new ListNode(i);node.next &＃61; newNode;node &＃61; node.next;}return head.next;}&＃64;Overridepublic String toString() {StringBuilder sb &＃61; new StringBuilder();ListNode node &＃61; this;while (node !&＃61; null) {sb.append(node.val).append("-->");node &＃61; node.next;}return sb.append("Null").toString();}
}

代码 – 遍历1

遍历的方法&＃xff0c;每次都创建一个新的节点&＃xff0c;这样交换&＃xff0c;不会受到原有链表的干扰。缺陷是head在最后&＃xff0c;指向了最后一个节点。

public ListNode reverseList(ListNode head) {ListNode current &＃61; null;ListNode previous &＃61; null;while (head !&＃61; null) {previous &＃61; current;current &＃61; new ListNode(head.val);current.next &＃61; previous;head &＃61; head.next;}return current;
}

代码 – 遍历2

这种遍历方法&＃xff0c;因为直接对current的遍历&＃xff0c;原有head不受影响。
注意&＃xff1a;

1. 先保存next节点&＃xff0c;再做顺序交换。
2. 最后返回的是previous节点&＃xff0c;因为在循环的最后都把current赋值给previous。

public ListNode reverseListWithoutChangeHead(ListNode head) {ListNode current &＃61; head;ListNode previous &＃61; null;ListNode nextNode;while (current !&＃61; null) {nextNode &＃61; current.next;current.next &＃61; previous;previous &＃61; current;current &＃61; nextNode;}return previous;
}

代码 – 递归

递归方法的技巧在于&＃xff0c;head为当前节点&＃xff0c;head.next.next &＃61; head; , 同时记得把head.next &＃61; null; , 递归到最后&＃xff0c;返回最后一个节点。

public ListNode reverseListWithRecursive(ListNode head) {while (head &＃61;&＃61; null || head.next &＃61;&＃61; null) {return head;}ListNode p &＃61; reverseListWithRecursive(head.next);head.next.next &＃61; head;head.next &＃61; null;return p;
}

测试方法

public static void main(String[] args) {int[] input &＃61; {1, 2, 3, 4, 5};ListNode head &＃61; ListNode.listNodeWithIntArray(input);System.out.println("Input: " &＃43; head.toString());ReverseLinkedList obj &＃61; new ReverseLinkedList();//ListNode result &＃61; obj.reverseList(head);//ListNode result &＃61; obj.reverseListWithoutChangeHead(head);ListNode result &＃61; obj.reverseListWithRecursive(head);System.out.println("Output: " &＃43; result.toString());}

运行结果

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

总结

链表反转&＃xff0c;容易出错&＃xff0c;不信请试试。

代码下载&＃xff1a;
https://github.com/zgpeace/awesome-java-leetcode/blob/master/code/LeetCode/src/common/ListNode.java
https://github.com/zgpeace/awesome-java-leetcode/blob/master/code/LeetCode/src/popular/ReverseLinkedList.java