Iterative and recursive Solution in Java


  • 0
    P

    Iterative solution is straightforward, we just need to change next pointer of current node to the previous node.

    public ListNode reverseList(ListNode head) {
        ListNode curr = head;
        ListNode newNext = null;
        ListNode newPrev;
        
        while (curr != null){
            newPrev = curr.next;
            curr.next = newNext;
            newNext = curr;
            curr = newPrev;
        }
        
        return newNext;
    }
    

    The idea for recursive solution is to divide the list into 3 parts:

    1. R : head of reversed list
    2. H : currently processing list
    3. Hprime : head of list that is not reversed yet.

    in each level of call we change pointer H.next to R, and process Hprime.

    public class Solution {
        public ListNode reverseList(ListNode head) {
           ListNode R = null;
           return reverse(head, R);
        }
        
        private ListNode reverse(ListNode H, ListNode R){
            if (H == null) return R;
            
            ListNode Hprime = H.next;
            H.next = R;
            R = H;
            return reverse(Hprime, R);
        }
    }

Log in to reply
 

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