Easy

Example

Challenge

Reverse it in-place and in one-pass
A linked list can be reversed either iteratively or recursively. Could you implement both?

Thinking

For iteration, we can always pop the second item and make the pop item as head in new list. Another one is changing every node next to father (see iterative2);
For recursion, we need to make sure each item will be the next item of his own next item (reverse: child becomes father and father becomes child’s child);

Complexity analysis

Iterative: Time complexity: O(n), Space complexity: O(1);
Recursive: Time complexity: O(n), Space complexity: O(n);

Solution

Java (iterative)

``````/**
* Definition for ListNode.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int val) {
*         this.val = val;
*         this.next = null;
*     }
* }
*/
public class Solution {
/**
*/
}
ListNode newNode = new ListNode(-1);
popNode.next = newNode.next;
newNode.next = popNode;
}
return newNode.next;
}
}
``````

Java (iterative2)

I think this one is better since we don’t have to create a dummy node.

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
}
ListNode prev = null;
while (curr != null) {
ListNode tmpNode = curr.next;
curr.next = prev;
prev = curr;
curr = tmpNode;
}
return prev;
}
}
``````

Java (recursive)

``````/**
* Definition for ListNode.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int val) {
*         this.val = val;
*         this.next = null;
*     }
* }
*/
public class Solution {
/**