leetCodeLinkedList.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/****************************************************************/
// Problem 1290: Convert Binary Number in a Linked List to Integer
// Link: https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer
// Solution 1: using an array to store the values, multiply each value by its bit later
// Time: O(2n), Space: O(n)
public int getDecimalValue(ListNode head) {
    if (head == null) { return 0; }

    // an array stores all the values
    List<Integer> vals = new ArrayList();
    int bit = 1;
    while (head != null) {
        vals.add(head.val);
        bit *= 2;
        head = head.next;
    }

    int sum = 0; 
    // iterate over the values, 
    // for each value multiply it with the its bit and add to the sum
    for (int i = 0; i < vals.size(); i++) {
        bit /= 2;
        sum += vals.get(i)*bit;
    }

    return sum;
}


// Solution 2: bit shifting
// Time: O(n), Space: O(1)
public int getDecimalValue(ListNode head) {
    if (head == null) { return 0; }

    int sum = 0;
    while (head != null) {
        sum = sum << 1;
        sum += head.val;
        head = head.next;
    }

    return sum;
}



/****************************************************************/
// Problem: 876: Middle of the Linked List 
// Link: https://leetcode.com/problems/middle-of-the-linked-list/
// Solution 1: traverse through the list to get the length, then calculate the mid index,
// traverse again and keep moving the head til index to get the result
// Time: O(1.5n), Space: O(1)
public ListNode middleNode(ListNode head) {
    if (head == null) { return null; }

    ListNode headCopy = head;

    // get the length of the list
    int length = 0;
    while (headCopy != null) {
        length += 1;
        headCopy = headCopy.next;
    }

    int mid = length / 2;
    // traverse until the mid index, then return the head
    for (int i = 0; i < mid; i++) {
        head = head.next;
    }

    return head;
}


// Solution 2: Have 2 heads, 
// 1 slow-running head: result head
// 1 fast-running head: traversing to the end
// Time: O(n), Space: O(1)
public ListNode middleNode(ListNode head) {
    if (head == null) { return null; }

    ListNode mid = head;

    int count = 1;
    while (head != null && head.next != null) {
        // slow runner
        if (count % 2 == 1) {
            mid = mid.next;
        }
        // fast runner
        head = head.next;
        count += 1;
    }

    return mid;
}



/****************************************************************/
// Problem: 206: Reverse Linked List
// Link: https://leetcode.com/problems/reverse-linked-list/
// Solution 1: Using 3 pointers
// 1 for prev, 1 for current, 1 for next
// Time: O(n), Space: O(1)
public ListNode reverseList(ListNode head) {
    if (head == null) { return null; }

    ListNode prev = null;
    // ListNode next = cur.next;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }

    return prev;
}


// Solution 2: Store the list into an Array, then update the nodes' values while reversing the array.
// Time: O(2n), Space: O(n)
public ListNode reverseList(ListNode head) {
    if (head == null) { return head; }

    ListNode nodeA = head;
    List<Integer> nodes = new ArrayList();

    while (nodeA != null) {
        nodes.add(nodeA.val);
        nodeA = nodeA.next;
    }

    ListNode nodeB = head;

    for (int i = nodes.size() - 1; i >= 0; i--) {
        nodeB.val = nodes.get(i);
        nodeB = nodeB.next;
    }

    return head;
}

// SOLUTION 3: Recursive
// Time: O(n), Space: O(n)
// TODO NOT WORKING StackOverFlow
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) { return head; }
    ListNode p = head.next;
    p.next = head;
    head.next = null;
    return reverseList(p);
}



/****************************************************************/
// Problem 83: Remove Duplicates from Sorted List
// Link: https://leetcode.com/problems/remove-duplicates-from-sorted-list/
// Solution 1: Recursive, bad :(
// check duplicates and remove them recursively
// Time: O(n), Space: O(n)
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) { return head; }
    ListNode p = head.next;
    if(head.val == p.val) {
        // p is a duplicate, remove pointer TO p and FROM p
        head.next = p.next;
        p.next = null;
        p = head;
    }
    deleteDuplicates(p);

    return head;
}


// Solution 2: Iterative
// using 2 pointers
// Time: O(n), Space: O(1) 
// TODO do i need to take care of pointer like "p"
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) { return null; }

    ListNode cur = head;
    ListNode p = head.next;
    while(p != null) {
        if (cur.val == p.val) {
            // p is a duplicate, remove pointers to p and from p.
            cur.next = p.next;
            p.next = null;
        } else {
            cur = p;
        }
        p = cur.next;
    }

    return head;
}



/****************************************************************/
// Problem 141: Linked List Cycle
// Link: https://leetcode.com/problems/linked-list-cycle/
// Solution 1: Using a hash table
// Traverse  and add nodes to a hashset, constantly check if the next pointer pointing to an old node
// Time: O(n), Space: O(1)
public boolean hasCycle(ListNode head) {
    if (head == null) { return false; }

    Set<ListNode> nodeSet = new HashSet<ListNode>();
    while (head.next != null) {
        nodeSet.add(head);
        // check if the next pointer creates a cycle
        if (nodeSet.contains(head.next)) {
            return true;
        }
        head = head.next;
    }

    return false;
}

// Solution 2: Slow and fast runners
// Time: O(n), Space O(1)
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) { return false; }

    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        if (fast == slow || fast.next == slow) {
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
    }

    return false;
}



/****************************************************************/
// Problem 160: Intersection of Two Linked Lists
// Link: https://leetcode.com/problems/intersection-of-two-linked-lists/
// Solution 1: Using a hash table
// Traverse list A and add nodes to a hashset, constantly check if the next node in B is already in A 
// Time: O(n^2), Space: O(n)

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    Set<ListNode> stackA = new HashSet<ListNode>();
    while(headA != null) {
        stackA.add(headA);
        headA = headA.next;
    }

    while(headB != null) {
        if (stackA.contains(headB)) { return headB; }
        headB = headB.next;
    }
    return null;
}


// Solution 2: Calculate length difference, move the head of the longer list until they're equally long
// Move both heads until they meet, return the intersection
// Time: O(m + n), Space O(1)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) { return null; }
    int lenA = 0;
    int lenB = 0;

    ListNode p = headA;
    while (p != null) {
        lenA += 1;
        p = p.next;
    }

    p = headB;
    while (p != null) {
        lenB += 1;
        p = p.next;
    }

    if (lenB > lenA) {
        // move headB "lenB - lenA" nodes forward
        for (int i = 0; i < lenB - lenA; i++) {
            headB = headB.next;
        }
    } else if (lenB < lenA) {
        // move headB "lenB - lenA" nodes forward
        for (int i = 0; i < lenA - lenB; i++) {
            headA = headA.next;
        }
    }

    // now both heads are at the same position, move them until the intersection
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }

    return headA;
}



/****************************************************************/
// Problem 234: Palindrome Linked List
// Link: https://leetcode.com/problems/palindrome-linked-list/
// Solution 1: Using an array to store all nodes
// Time: O(1.5n), Space: O(n)
// TODO NOT WORKING

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<Integer>();
    while(head != null) {
        vals.add(head.val);
        head = head.next;
    }

    int size = vals.size();
    for(int i = 0; i < size/2; i++) {
        if (vals.get(i) != vals.get(size - 1 - i)) {
            System.out.print("a");
            return false;
        }
    }

    return true;
}


// Solution 2: Reverse first half, and compare to the second
// Time: O(n), Space O(1)
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) { return true; }

    // STEP 1: REVERSE first half
    ListNode prev = null;
    ListNode p = head;
    while (p != null && p.next != null) {
        ListNode cur = head;
        head = head.next;
        p = p.next.next;

        // reverse pointers
        cur.next = prev;
        prev = cur;
    }

    // makes m the head of second half
    if (p == null) { // list has an even length
        p = head;
    } else { // list has an odd length
        p = head.next;
    }
    head = prev;

    // STEP 2: COMPARE reversed first half and second half
    while (head != p) {
        if (head.val != p.val) {
            return false;
        }
        head = head.next;
        p = p.next;
    }

    return true;
}



/****************************************************************/
// Problem 203: Remove Linked List Elements
// Link: https://leetcode.com/problems/remove-linked-list-elements/
// Solution 1: recursive
// Time: O(n), Space: O(n)
public ListNode removeElements(ListNode head, int val) {
    if (head == null) { return null; }
    if (head.val == val) { return removeElements(head.next, val); }

    ListNode p = head.next;
    while (p != null && p.val == val) {
        ListNode dummy = p;
        head.next = p.next;
        p = p.next;
        dummy.next = null;
    }
    removeElements(p, val);
    return head;
}


// Solution 2: Iterative, skip a node when its val == val
// Time: O(n), Space: O(1)
public ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0, head);
    ListNode p = dummy;

    while (head != null) {
        if(head.val == val) {
            // skip the nodes with "val"
            p.next = head.next;
        } else {
            p = head;
        }
        head = head.next;
    }

    return dummy.next;
}



/****************************************************************/
// Problem 53. Maximum Subarray
// Link: https://leetcode.com/problems/maximum-subarray/
// Solution 1: Idek, each number is either part of a subarray or the beginning of one
// Time: O(n), Space: O(1)
public int maxSubArray(int[] nums) {
    int tempMax = nums[0];
    int max = nums[0];

    for (int i = 1; i < nums.length; i++) {
        int num = nums[i];
        int sum = tempMax + num;

        tempMax = num > sum ? num : sum;
        max = tempMax > max ? tempMax : max;
    }

    return max;
}



/****************************************************************/
// Problem 66. Plus One
// Link: https://leetcode.com/problems/plus-one/
// Solution 1: Add one to the number in array format, if not overflowed, return the number.
//              Else increase length by 1 and return.
// Time: O(n), Space: O(n)
public int[] plusOne(int[] digits) {
    int length = digits.length;

    for (int i = length - 1; i >= 0; i--) {
        // add 1 and return the number if this digit is < 9
        if (digits[i] < 9) {
            digits[i]++;
            return digits;
        } 

        // the sum has a carry
        digits[i] = 0;
    }

    // check if the left-most digit does not have a carry
    if(digits[0] != 0) {
        return digits;
    } 

    // if it does, increase length by 1
    int[] result = new int[length + 1];
    result[0] = 1;
    for (int i = 0; i < length; i++) {
        result[i + 1] = digits[i];
    }

    return result;
}