题目
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?
解法思路（一）
- 这个解法有点拧巴：从第二个节点开始，依次链到 head 的左边；
- 具体做法是：先把要链到左边的节点“空出来”，所谓“空出来”就是，该节点左边的节点，通过它，指向它的右节点，而该节点像一座桥，将其左右节点相连，从而“解放”自己，使自己可以指向别的节点；
- 而被“解放”的节点将链到逐渐链到 head 左边的链表的最后；
解法实现（一）
时间复杂度
- O(N)；
空间复杂度
- O(1)；
关键字
链表反转
实现细节
- 对空链表要单独处理；
package leetcode._206;
public class Solution206_1 {
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode bridge;
ListNode cursor = head;
ListNode tail = head;
while (cursor.next != null) {
bridge = cursor.next;
cursor.next = bridge.next;
bridge.next = tail;
tail = bridge;
}
return tail;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode head2 = (new Solution206_1()).reverseList(head);
System.out.println(head2);
}
}
class ListNode {
public int val;
public ListNode next = null;
public ListNode(int x) {
val = x;
}
// 根据n个元素的数组arr创建一个链表
// 使用arr为参数，创建另外一个ListNode的构造函数
public ListNode (int[] arr){
if(arr == null || arr.length == 0)
throw new IllegalArgumentException("arr can not be empty");
this.val = arr[0];
ListNode curNode = this;
for(int i = 1 ; i < arr.length ; i ++){
curNode.next = new ListNode(arr[i]);
curNode = curNode.next;
}
}
// 返回以当前ListNode为头结点的链表信息字符串
@Override
public String toString(){
StringBuilder s = new StringBuilder("");
ListNode curNode = this;
while(curNode != null){
s.append(Integer.toString(curNode.val));
s.append(" -> ");
curNode = curNode.next;
}
s.append("NULL");
return s.toString();
}
}
解法思路（二）
- 维护了 3 个指针，
pre，cur，next，在cur遍历链表的时候，直接改变cur.next的指向，使其指向其前一个节点，然后 3 个指针齐向右移一位；
解法实现（二）
时间复杂度
- O(N)；
空间复杂度
- O(1)；
关键字
链表反转
实现细节
- 注意进入循环的条件
cur != null，这样避免了单独处理head == null的情况；
package leetcode._206;
public class Solution206_2 {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
ListNode head = new ListNode(nums);
System.out.println(head);
ListNode head2 = (new Solution206_2()).reverseList(head);
System.out.println(head2);
}
}
附 - ListNode
class ListNode {
public int val;
public ListNode next = null;
public ListNode(int x) {
val = x;
}
// 根据n个元素的数组arr创建一个链表
// 使用arr为参数，创建另外一个ListNode的构造函数
public ListNode (int[] arr){
if(arr == null || arr.length == 0)
throw new IllegalArgumentException("arr can not be empty");
this.val = arr[0];
ListNode curNode = this;
for(int i = 1 ; i < arr.length ; i ++){
curNode.next = new ListNode(arr[i]);
curNode = curNode.next;
}
}
// 返回以当前ListNode为头结点的链表信息字符串
@Override
public String toString(){
StringBuilder s = new StringBuilder("");
ListNode curNode = this;
while(curNode != null){
s.append(Integer.toString(curNode.val));
s.append(" -> ");
curNode = curNode.next;
}
s.append("NULL");
return s.toString();
}
}
