public ListNode reverseList(ListNode head) {
/* iterative solution */
ListNode newHead = null;
while (head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
public ListNode reverseList(ListNode head) {
/* recursive solution */
return reverseListInt(head, null);
}
private ListNode reverseListInt(ListNode head, ListNode newHead) {
if (head == null)
return newHead;
ListNode next = head.next;
head.next = newHead;
return reverseListInt(next, head);
}
Inplace iterative and recursive Java solution


Thanks for sharing. But in your iterative solution, this line of code:
ListNode next = head.next;
essentially takes O(n) EXTRA space, right? So is this really an inplace solution? I don't think so. I mean if we're using O(n) EXTRA space, we can just simply store all values and construct a new linked list, no?

said in Inplace iterative and recursive Java solution:
ListNode next = head.next;
I suggest you not to use "next" when you produce a name of ListNode, cause the word "next" is really special, right?

@fanfeng_boston This takes constant space just for temporary value, so that it must be O(1), and in place

@LeeLom iterative solution is really O(1) space and O(n) time. I see no way to improve the complexity.


@braydenCN Thanks for pointing out. Yes, that might be a problem causing stackoverflow.


@braydenCN said in Inplace iterative and recursive Java solution:
@Harrywithcode vars of "pre, cur, next" are frequently used in LinkList solution
Wondering why downvotes here and in previous posts. these are meaningful discussions.


@marrow Normally lists should not have loops in them. It should be specially noted and handled.