Reverse Linked List

Reverse a singly linked list.

Question

Reverse a singly linked list. (In both iteration and recursive way)

Example:

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

Analyzation

1. Iteration Method is shown below. Very intuitive way.

2. Recursive Method is shown below. Each recursive step adds up to a stack.

The Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
        // iteration
        
        ListNode prev = null;
        ListNode next = null;
        ListNode curr = head;
        
        while(curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        head = prev;
        
        return head;
        
        
        // recursive
        
        if(head == null) { 
            return head; 
        } 
  
        // last node or only one node 
        if(head.next == null) { 
            return head; 
        } 
          
        ListNode newHeadNode = reverseList(head.next); 
        
        // change references for middle chain 
        head.next.next = head; 
        head.next = null; 
  
        // send back new head node in every recursion 
        return newHeadNode; 
    }
}

Time & Space Complexity

• Time Complexity: Since we create a loop so it is O(n).
• Space Complexity: Since we did not create any data structure, the Space Complexity is O(1).