linkedList.java

/*
Linked list stores a single instance variable that is a pointer to the first Node in the list

Insert into a Linked List:
Step 1: Create new node
Step 2: Set next to current head
Step 3: Set the new node to be the head

Remove from a Linked List:
Step 1: Set the pointer from head to the next node in the list

Traversing a Linked List
Step 1: Set a temporary pointer called current to the head -> Current = self.head
Step 2: Process current.value -> print(current.value)
Step 3: Set current to its next -> current = current.next


*/

class MyLinkedList {
    
    int length;
    Node head;
    class Node {
        int val;
        Node next;
        Node(int x) {
            this.val = x;
        }
    }
    
    public MyLinkedList() {
        this.length = 0;
        this.head = null;
    }
    
    
    public int get(int index) {
        if (index < 0 || index >= this.length) {
            return -1;
        }
        Node curr = head;
        int counter = 0;
        while (counter != index) {
            cur = cur.next;
            counter++;
        }
        return curr.val;
    }
    
    public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = this.head;
        this.head = newNode;
        this.length++;
    }
    
    public void addAtTail(int val) {
        Node newNode = new Node(val);
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = newNode;
        newNode.next = null;
        this.length++;
    }
}

/*
cur.next = prev
prev = cur
cur = cur.next
*/

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


/*
set fast & slow pointer 
have a while loop with fst != null & fast.next != null
slow = slow.next
fast = fast.next.next

if (slow == fast) {
    return true
}
return false


*/


public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    return false;
}


/*
-> find the length of both the lists, then compare which list 
is bigger. if list A > list B then find the difference of listA
and listB else vice versa. Using the difference travese the 
list to that location and then compare the values if equal
return the value else null
O(N) runtime
O(1) space
*/

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode curA = headA;
    ListNode curB = headB;
    int lengthA = 0;
    int lengthB = 0;
    while (curA != null) {
        curA = curA.next;
        lengthA++;
    }
    
    while (curB != null) {
        curB = curB.next;
        lengthB++;
    }
    
    if (lengthA > lengthB) {
        lengthA = lengthA - lengthB;
        while(lengthA != 0) {
            curA = curA.next;
            lengthA--;
        }
    }
    
    if (lengthB > lengthA) {
        lengthB = lengthB - lengthA;
        while(lengthB != 0) {
            curB = curB.next;
            lengthB--;
        }
    }
    
    while (curA != null || curB != null) {
        if (curA.val == curB.val) {
            return curA.val;
        }
        curA = curA.next;
        curB = curB.next;
    }
    return null;
}


/*
have two pointers, fast & slow once fast.next pointer is null
stop. 
now pass the slow pointer copy to reverse the linked list.
Reverse the list until the end (start off with initalizing prev & while
cur!= null, the cur.next = prev, prev = cur cur = cur.next return prev)
reset slow pointer and while slow != fast if (slow.val == fast.val) slow = slow.next
fast = fast.next retrurn true else false
O(N) runtime
O(1) space
*/

public boolean isPalindrome(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    ListNode start = head;
    ListNode prev = null;
    
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    fast = head;
    slow = reverseList(slow)
    while (slow != null) {
        if(slow.val != fast.val) {
            return false;
        }
        fast = fast.next;
        slow = slow.next;
    }
    return true;
}


public boolean reverseList(head) {
    cur = head.next;
    prev = head
    while(cur != null) {
            cur.next = prev;
            prev = cur;
            cur = cur.next
        }
    return cur;
}

/*
first compute the length of the list and subtract n then traverse to that location
using cur.next = cur.next.next; 

*/
 public ListNode removeNthFromEnd(ListNode head, int n) {
    int length = 0;
    ListNode cur = head;
    while(cur != null) {
        cur = cur.next;
        length++;
    }
    length = (length - n) + 1;
    while(length != 0) {
        cur = cur.next;
    }
    cur.next = cur.next.next;
    
    return cur
        
}

/*
Reorder List:
Find the middle of the List
Reverse the half after middle
Start reorder one by one
*/


public void reorderList(ListNode head) {
    if (head==null) return;
    ListNode head2 = Split(head);
    head2 = Reverse(head2);
    Merge(head, head2);
}

public ListNode Split(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    ListNode head2 = slow.next;
    slow.next = null;
    return head2;
}


public ListNode Rverse(ListNode head) {
    ListNode curr = head;
    ListNode prev = null;
    
    while(curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

public ListNode Merge(ListNode head1, ListNode head2){
    ListNode curr1 = head1;
    ListNode curr2 = head2;
    
    while(curr1 != null && curr2 != null) {
        ListNode next1 = curr1.next;
        ListNode next2 = curr2.next;
        
        curr1.next = curr2;
        curr2.next = next1;
        
        curr1 = next1;
        curr2 = next2;
    }
    return head1;
}