题目
Reverse a singly linked list.
单链表反转
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
1.迭代法：
public ListNode reverseList(ListNode head) {
ListNode newHead = null;
while(head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
reverseList.png
时间复杂度O(n)
2.递归法
private ListNode reverseList2(ListNode head) {
if (head == null) {
return null;
}
return reverseList(head, null);
}
private ListNode reverseList(ListNode head, ListNode newHead) {
if (head == null && newHead != null) {
return newHead;
}
ListNode next = head.next;
head.next = newHead;
return reverseList(next, head);
}
时间复杂度: O(n)
