1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode prev = null;
ListNode current = head;
while (current != null) {
ListNode next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
}
|
这个是非递归解法.
时间复杂度: O(n)
空间复杂度: O(1)
1
2
3
4
5
6
7
8
9
10
| 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;
}
}
|
这个是递归解法. 递归函数的功能是给它一个node, 它能反转它所代表的list并且返回新的head.
时间复杂度: O(n)
空间复杂度: O(n)
