1.4 Reverse LinkedList 206
Description
Reverse a singly linked list.
Hint
A linked list can be reversed either iteratively or recursively. Could you implement both?
Method
recursive
iterative
Time & Space
recursive : O(n)
iterative : O(n)
Code
iterative :
public ListNode reverseList(ListNode head){
if (head == null || head.next == null){
return head;
}
ListNode newHead = null;
while (head != null){
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
recursive:
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null){
return head;
}
return helper(head, null);
}
public ListNode helper(ListNode head, ListNode newHead){
if (head == null){
return newHead;
}
ListNode next = head.next;
// reverse current head
head.next = newHead;
return helper(next, head);
// next and head as entry for next recursive
}