Iterative and Recursive Java Solutions, 0ms and 1ms


  • 0
    M

    In both the recursive solution and iterative solution, we must begin by saving the state of head's next node. We then point head backwards to a null node.

    In the recursive solution, we pass two parameters. We pass an iterator head, which allows us to reach the end of the list. We also pass which node the head should point to. The crucial step here is saving the node which used to be head's next node.

    In the iterative solution, the idea is similar. Instead of passing a reference to nodes, we simply keep a node variable to point to the net node. This is more efficient.

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public ListNode reverseList(ListNode head) {
            if (head == null) return head;
            return reverse(head, null);
        }
        
        private ListNode reverse(ListNode head, ListNode newest) {
            if (head.next == null) {
                head.next = newest;
                return head;
            } else {
                ListNode save = head.next;
                head.next = newest;
                return reverse(save, head);
            }
        }
        
        public ListNode reverseListIterative(ListNode head) {
            ListNode newest = null;
            while (head != null) {
                ListNode save = head.next;
                head.next = newest;
                newest = head;
                head = save;
            }
            return newest;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.