題目:
Reverse a singly linked list.
Hint:
A linked list can be reversed either iteratively or recursively. Could you implement both?
分析:
以下是Iterative方式的代碼
class Solution {
public ListNode reverseList(ListNode root) {
if(root == null) return null;
ListNode prev = null, curr = root;
while(curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
以下是Recursive方式的代碼
class Solution {
public ListNode reverseList(ListNode root) {
if(root == null || root.next == null) return root;
ListNode next = root.next;
ListNode ret = reverseList(root.next);
next.next = root;
root.next = null;
// Always only return the tail of the whole list
return ret;
}
}
