Description
Reverse a singly linked list.
Hint:A linked list can be reversed either iteratively or recursively. Could you implement both?
Solution
Iterative
可以用head作为curr，这样可以省略一个局部变量。
另外prev初始为null是比较简洁的写法。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
Recursive
递归的写法还蛮tricky的，重点是保证reverse后原链表的head指向reverse后的链表尾部，而不是指向null。举个例子：
- 原链表：1->2->3
- 一层递归后：1->2<-3
- 二层递归后：1<-2<-3
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
