Thursday, November 6, 2014

Facebook: Print the nodes of a linked list in reverse order

Print the nodes of a linked list in reverse order
Method 1: Recursive Solution:
Traverse the linked list until the end, then print the nodes in reverse order. 

Code (Java):
public class Solution {
    public void printListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        
        printListReverse(head.next);
        System.out.print(head.val + " ");
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        
        ListNode head = new ListNode(0);
        ListNode p = head;
        for (int i = 1; i < 10; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
        p.next = null;
        
        sol.printListReverse(head);
    }
}

Method 2: Iterative using a stack
Traverse the nodes of the list and add them into a stack. Then pop the stack and print out the values.

Code (Java):
import java.util.*;

public class Solution {
    public void printListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        
        Stack<Integer> stack = new Stack<Integer>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
        
        System.out.println(" ");
    }
}

Method 3: Reverse the linked list, then print the nodes in order. 
Time: O(n) + O(n) = O(n)
Space: O(1)
Disadvantage: Modify the linked list. 

Code (Java):
public class Solution {
    public void printListReverse(ListNode head) {
        if (head == null) {
            return;
        }
        
        ListNode newHead = reverseList(head);
        
        while (newHead != null) {
            System.out.print(newHead.val + " ");
            newHead = newHead.next;
        }
        
        System.out.println(" ");
    
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        
        return prev;
    }
}

No comments:

Post a Comment