一个月刷完cc150

2.1 Remove Dups
Problem:
Write code to remove duplicates from an unsorted linked list.

Analysis:
Use a set to differentiate duplicate values.

Code: O(n) time, O(n) space
Public void removeDup(ListNode head){
    If (head == null || head.next == null) return;
    ListNode dummy = head, previous = null;
    Set<ListNode> set = new HashSet<>();
    While (dummy != null){
        If (set.contains(dummy.val)) {
            previous.next = dummy.next;
        } else {
            Set.add(dummy.val);
            Previous = dummy;
        }
        Dummy = dummy.next;
    }
}

Follow up: No Buffer Allowed
Analysis:
Use runner pointer to remove duplicate.

Code: O(n^2) time, O(1) space
Public void removeDup(ListNode head){
    If (head == null || head.next == null) return;
    ListNode dummy = head, runner = dummy;
    While (dummy != null){
        While (runner.next != null){
            If (runner.next.val == dummy.val){
                Runner.next = runner.next.next;
            } else {
                Runner = runner.next;
            }
        }
        Dummy = dummy.next;
    }
}

2.2 Return Kth to Last
Problem:
Implement an algorithm to find the kth to last element of a singly linked list.

Analysis:
We can use two pointers p1 and p2, and p2 is k nodes after p1. Then move p1 and p2 together. When p2 hit the end, p1 is at nth to last node.

Code:
Public Node kthToLast(Node head, int k){
    Node p1= head;
    Node p2 = head;
    For (int I = 0; I < k; I++) {
        P2 = p2.next;
    }
    While (p2 != null){
        P1 = p1.next;
        P2 = p2.next;
    }
    Return p1;
}

2.3 Delete Middle Node
Problem:
Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.
Example:
lnput:the node c from the linked lista->b->c->d->e->f
Result: nothing is returned, but the new linked list looks likea->b->d->e- >f

Analysis:
We have no access to head but have access to target node. We can move next node’s data to this node and delete next node.

Code:
Public void deleteNode(Node node){
    Node tmp = node.next;
    node.data = tmp.data;
    node.next = tmp.next;
}

2.4 Partition
Problem:
Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.
Example:
Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1[partition=5] Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

Analysis:
We can use two lists to each store values greater and smaller than given value. Then merge them.

Code:
Public Node partition(Node head, int x) {
    Node smallerStart = null, largerStart = null, smallerEnd = null, largerEnd = null;
    While (head != null){           
        Node next = head.next;
        head.next = null;
        If (head.val < x){
            If (largerStart == null){
                largerStart = head;
                largerEnd = largerStart;
            } else{
                largerEnd.next = head;
                largerEnd = largerEnd.next;
            }
        } else {
            If (smallerStart == null){
                smallerStart = head;
                smallerEnd = smallerStart;
            }    else{
                smallerEnd.next = head;
                smallerEnd = smallerEnd.next;
            }
        }
        Head = next;
    }
    If (smallerEnd == null) return largerStart;
    smallerEnd.next = largerStart;
    Return smallerStart;
}

2.5 Sum Lists
Problem:
You have two numbers represented by a linked list, where each node contains a single digit.The digits are stored in reverse order, such that the 1 's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
Example:
Input:(7-> 1 -> 6) + (5 -> 9 -> 2).That is,617 + 295. Output:2 -> 1 -> 9.That is,912.

Analysis:
We can add digits from head as from least significant number. Manage well the carry.

Code:
public ListNode addTwoNumbers(ListNode n1, ListNode n2) {
    ListNode cur = new ListNode(0);
    ListNode dummy = cur;
    int carry = 0;
    while(n1!=null || n2!=null || carry!=0){
        int x=n1==null?0:n1.val;
        int y=n2==null?0:n2.val;
        int sum=x+y+carry;
        carry=sum/10;
        cur.next=new ListNode(sum%10);
        cur=cur.next;
        n1=n1==null?null:n1.next;
        n2=n2==null?null:n2.next;
    }
    return dummy.next;
}

Follow up:
Suppose the digits are stored in forward order. Repeat the above problem.
Example:
lnput:(6 -> 1 -> 7) + (2 -> 9 -> 5).That is,617 + 295. Output:9 -> 1 -> 2.That is,912.

Analysis:
We can use a stack to store numbers and pop to use above method.

Code:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        int carry = 0, num1 = 0, num2 = 0, sum = 0;
        ListNode ans = new ListNode(0);
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        while (carry != 0 || (!stack1.isEmpty() || !stack2.isEmpty())) {
            num1 = stack1.isEmpty()? 0: stack1.pop();
            num2 = stack2.isEmpty()? 0: stack2.pop();
            sum = num1 + num2 + carry;
            carry = sum / 10;
            ListNode tmp = ans.next;
            ans.next = new ListNode(sum % 10);
            ans.next.next = tmp;
        }
        return ans.next;
    }

2.6 Palindrome
Problem:
Implement a function to check if a linked list is a palindrome.

Analysis:
We need to go through list and compare reversely. Stack data type can do this. And to reach middle of the list, we can use slow and fast pointers. Also take care of odd length, where fast pointer is at the end node but not null when slow pointer is at middle.

Code:
Public boolean isPalindrome(Node head){
    Node fast = head, slow = head;
    Stack<Integer> stack = new Stack<>();
    While (fast .next != null){
        Fast = fast.next.next;
        Stack.push(slow.val);
        Slow = slow.next;
    }
    If (fast != null){
        Slow = slow.next;
    }
    While (slow != null){
        If (slow.val != stack.pop()) return false;
        Slow = slow.next;
    }
    Return true;
}

2.7 Intersection (leetcode 160. Intersection of Two Linked Lists)
Problem:
Given two (singly) linked lists, determine if the two lists intersect. Return the inter- secting node. Note that the intersection is defined based on reference, not value.That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.

Analysis:
We can find their lengths. Then move their head pointer to the same start. Finally iterate at the same time and get the intersection when references are equal.

Code:
Public Node intersection(Node n1, Node n2){
    Int len1 = length(n1);
    Int len2 = length(n2);
    While (len1 < len2){
        N2 = n2.next;
        Len2—;
    }
    While (len2 < len1){
        N1 = n1.next;
        len1--;
    }
    While (n1 != n2){        
        N1 = n1.next;
        N2 = n2.next;
    }
    Return n1;
}

Public int length(Node n){
    Int ans = 0;
    While (n1 != null){
        N1 = n1.next;   
        ans++;
    }
    Return ans;
}

2.8 Loop Detection
Problem:
Given a circular linked list, implement an algorithm that returns the node at the
beginning of the loop.
Definition:
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
Example:
Input: A -> B -> C -> D -> E -> C[thesameCasearlier]
Output: C

Analysis:
We use fast and slow pointers. Assume slow pointer enters the loop after k steps, so fast pointer is already in the loop and has gone 2k steps. So fast pointer is k steps longer slow pointer in the loop, and is loopLen-k steps shorter than slow pointer. Then fast pointer will be 1 step nearer slow pointer each unit time. So after loopLen-k steps, fast pointer and slow pointer will be at same spot, and is k steps shorter than loop start. Now we move slow pointer at head of list, and fast pointer at k before loop start. Now move two pointers at same pace, so they will meet at loop start, because they are both k steps before loop start.

Code:
Public Node loopDetection(Node head){
    Node fast = head, slow = head;
    While (fast != null && fast.next != null && slow != fast){
        Slow = slow.next;
        Fast = fast.next.next;
    }
    If (fast == null || fast.next == null) return null;
    Slow = head;
    While (slow != fast){
        Slow = slow.next;
        Fast = fast.next;
    }   
    Return slow;
}

楼主加油！⛽️

3.4 Queue via Stacks
Problem:
Implement a MyQueue class which implements a queue using two stacks.

Analysis:
To implement Queue, we will reverse the output order with another stack. To optimize time when peek() or remove() which requires oldest element, and so requires reverse, we can reverse only when the oldest stack is empty, which is referred to as “lazy” approach.

Code:
Public class MyQue<Integer>{
    Private Stack<Integer> newest;
    Private Stack<Integer> oldest;
    Public MyQue<Integer>(){
        Newest = new Stack<Integer>();
        Oldest = new Stack<Integer>();
    }
    Public int size(){
        Return oldest.size() + newest.size();
    }
    Public void add(int x){
        Newest.push(x);
    }
    Public int peek(){
        Reverse();
        Return oldest.peek();
    }
    Public int remove(){
        Reverse();
        Return oldest.pop();
    }
    Public void reverse(){
        If(oldest.isEmpty()){
            While(!newest.isEmpty()){
                Oldest.push(newest.pop());
            }
        }
    }
}