Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL 
Output: 5->4->3->2->1->NULL 

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
    }
}

Idea - 1

If we process the list left to right, then for a node c and next node n, if we recursively reverse the part right of c then c must go as the next of n. So, we need to save reference to n while processing node c. The algorithm takes time and space .

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseFrom(head);
    }
    
    private ListNode reverseFrom(ListNode c)
    {
        if(c==null || c.next == null)
        {
            return c;
        }
        
        ListNode n = c.next;
        c.next = null;

        ListNode restReversed = reverseFrom(n);
        
        n.next = c;
        
        return restReversed;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.9 MB, less than 14.19% of Java online submissions for Reverse Linked List.

Idea - 2

We could insert each node at the front of a new list. Time and space .

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        ListNode q = dummy;
        
        while(p != null)
        {
            ListNode pnext = p.next;
            p.next = q.next;
            q.next = p;
            
            p = pnext;
        }
        
        return dummy.next;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.9 MB, less than 9.02% of Java online submissions for Reverse Linked List.