50 DSA-Questions: #23, #24, #25

#23. Encode and Decode Strings

Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and decoded back to the original list of strings.

public class Exercise23 {
    private static final String[] INPUT = {"Gina89", "loves_", "Pluto"};
    private static final String FIRST_SEP = "::";
    private static final String WORD_SEP = "#";
    private static final String INSIDE_SEP = "=";

    private String encode() {
        // format NR_CUVINTE::NR_CHAR=STR#NR_CHAR=STR#.....
        StringBuilder code = new StringBuilder(INPUT.length + FIRST_SEP);
        for (String word : INPUT) {
            code.append(word.length()).append(INSIDE_SEP).append(word).append(WORD_SEP);
        }
        return code.toString();
    }

    private String[] decode(String coded) {
        int numberOfWords = Integer.parseInt(coded.substring(0, coded.indexOf(FIRST_SEP)));
        String result[] = new String[numberOfWords];
        String splitCode[] = coded.substring(coded.indexOf(FIRST_SEP) + FIRST_SEP.length()).split(WORD_SEP);

        int i = 0;
        for (String code : splitCode) {
            result[i++] = code.substring(code.indexOf(INSIDE_SEP)+1);
        }

        return result;
    }

    private void solve() {
        String coded = encode();
        System.out.println(coded);

        String[] result = decode(coded);
        for (String res : result) {
            System.out.print(res + " ");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        new Exercise23().solve();
    }
}

#24. Reverse Linked Lists

Given the head of a singly linked list, reverse the list, and return the reversed list.

class Solution {
    public ListNode reverseList_newList(ListNode head) {
        if (head == null) {
            return null;
        }

        Stack<Integer> stack = new Stack<>();
        while (head != null) {
            stack.push(head.val);
            head = head.next;
        }

        ListNode result = stack.empty() ? new ListNode() : new ListNode(stack.pop());
        ListNode node = result;
        while (!stack.empty()) {
            ListNode newNode = new ListNode(stack.pop());
            node.next = newNode;
            node = newNode;
        }
        
        return result;
        // O(n) spatial (stiva + rezultat)
    }

    public ListNode reverseList_inPlace(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode p1 = head, p2 = head;

        while (p2 != null && p2.next != null) {
            stack.push(p1);
            p1 = p1.next; // pas 1
            p2 = p2.next.next; // pas 2, ajunge la mijloc
        }

        boolean odd = p2 != null && p2.next == null;
        if (odd) {
            p1 = p1.next;
        }

        while (p1 != null) {
            swapData(p1, stack.pop());
            p1 = p1.next;
        }

        return head;
    }

    private void swapData(ListNode pluto, ListNode jupiter) {
        Integer data = pluto.val;
        pluto.val = jupiter.val;
        jupiter.val = data;
    }

    class Wrapper {
        ListNode head;
        Wrapper(ListNode head) {
            this.head = head;
        }
    }

    public ListNode reverseList_rec(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode aux = head;
        int size = 1;
        while (aux.next != null) {
            size++;
            aux = aux.next;
        }

        Wrapper wrap = new Wrapper(head);
        recurse(head, wrap, 0, size);
        return head;
    }

    private void recurse(ListNode node, Wrapper p1, int index, int size) {
        if (node.next != null) {
            recurse(node.next, p1, index + 1, size);
        }
        if (index < size/2) {
            swapData(node, p1.head);
        }
        p1.head = p1.head.next;
    }
}

#25. Linked List Cycle

Given the head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Return true if there is a cycle in the linked list. Otherwise, return false.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode p1 = head, p2 = head;
        while (p1.next != null &&  p2.next != null && p2.next.next != null) {
            p1 = p1.next; // p1 goes 1 step forward
            if (p1 == null) {
                return false;
            }
            p2 = p2.next;
            if (p2 == null) {
                return false;
            } else {
                p2 = p2.next; // p2 goes 2 steps forward
            }
            if (p1 == p2) {
                return true;
            }
        }
        return false;
    }
}