2. Linked List

好题

• Remove duplicates from sorted list II

• Reverse Nodes in k-Group

• Insert into a sorted circular linked list

• Flatten a Multilevel doubly linked list

• LRU Cache

Reverse Linked List

• Iterative & recursive solution 都需要掌握

public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next= head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    
//recursive
public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

Remove duplicates from sorted list II

• [1,2,2,4,4,5] -> [1,5]

• [1,1,2] ->[2]

• [1,2,2] ->[1]

public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy, cur = dummy.next;
        while (cur != null && cur.next != null) {
            ListNode next = cur.next;
            boolean dup = false;
            while (next != null && cur.val == next.val) {
                dup = true;
                next = next.next;
            }
            if (dup) {
                prev.next = next;//connect prev.next to next directly
            } else {
                prev = cur; //move prev 1 step forward
            }
            cur = next;
        }
        return dummy.next;
    }

Remove Nth Node from End of List

• slow, fast pointer

public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

Swap Nodes in Pairs

• reverse Nodes in K-Group, k = 2的情况

• 需要掌握both recursive and iterative approach

//recursive solution
public ListNode swapPairs(ListNode head) {
        if (head == null||head.next == null) return head;
        ListNode next = head.next;
        head.next = swapPairs(head.next.next);
        next.next = head;
        return next;
}

• Iterative solution

public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        while (head != null && head.next != null) {
            //define nodes to be swapped
            ListNode first = head, second = head.next;
            //swap first and second
            prev.next = second;
            first.next = second.next;
            second.next = first;
            //set prev and hand pointer
            prev = first;
            head = first.next;
        }
        return dummy.next;
    }

Reverse Nodes in k-Group

• Swap nodes in pairs的general solution

• split list into 2 parts, first k nodes and rest

  • if list.size() < k, return original list

  • else: reverse first K nodes and recursively reverseKGroup for the rest of nodes

class Solution {
    /*
    1.split list into 2 parts, first k nodes and rest
    2.if list.size() < k, return original list
    3.else: reverse first K nodes and recursively reverseKGroup for the rest of nodes 
    */
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        int cnt = 0;
        while (cnt < k && prev.next != null) {
            prev = prev.next;
            cnt++;
        }
        if (cnt < k) {
            return head;
        }
        ListNode newHead = prev.next;
        prev.next = null;
        newHead = reverseKGroup(newHead, k);
        head = reverse(head);
        dummy.next = head;
        prev = dummy;
        while (prev != null && prev.next != null) {
            prev = prev.next;
        }
        prev.next = newHead;
        return dummy.next;
        
    }
    ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

• Iterative solution

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) return head;
        int n = 0;
        for (ListNode i = head; i != null; i = i.next) n++;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy, cur = head;
        while (n >= k) {
            ListNode tail = prev;// tail is last non-null node for K group
            int i = 0;
            while (i++ < k) {
                tail = tail.next;
            }
            ListNode next = tail.next;
            tail.next = null;
            ListNode newHead = reverse(cur);
            prev.next = newHead;
            while (newHead != null && newHead.next != null) {
                newHead = newHead.next;
            }
            newHead.next = next;
            prev = newHead;
            
            cur = next;
            n -= k;
        }
        prev.next = cur;
        return dummy.next;
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

Reorder List

• 基础题，适合拿来练手

• 3步走

• fast, slow指针找mid

• reverse seond Half

• merge 2 lists

class Solution {
    /*
    find mid, cut into 2 lists(list1 >= list2)
    reverse list2
    merge list1 and list2
    */
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        ListNode newSecond = reverse(second);
        //merge
        fast = head;
        slow = newSecond;
        while (slow != null) {
            ListNode fNext = fast.next;
            ListNode sNext = slow.next;
            fast.next = slow;
            slow.next = fNext;
            fast = fNext;
            slow = sNext;
        }
    }
    
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

Insert into a sorted circular linked list

• 好题

• 首先分成两种情况，head 是否为空

• 如果head不为空的话，先找到max和min

• 然后分两种情况讨论

  • insertVal >= max || insertVal <= min

  • insertVal在min和max之间

• 这题要注意避免死循环的情况

/*
1. if list is empty, then create a new head and return
2. otherwise find out the max Node, then min = max.next
2.1 if (insertVal >= max.val || insertVal <= min.val) insert between min and max
2.2 otherwise find the correct place to insert
*/
class Solution {
    public Node insert(Node head, int insertVal) {
        Node node = new Node(insertVal);
        //empty list
        if (head == null) {
            node.next = node;
            return node;
        }
        Node max = head;
        while (max.val <= max.next.val && max.next != head) {//不是max.next != max, 死循环
            max = max.next;
        }
        Node min = max.next;
        Node cur = min;
        if (insertVal >= max.val || insertVal <= min.val) {
            max.next = node;
            node.next = min;
        } else {
            while (cur.next.val < insertVal) {
                cur = cur.next;
            }
            Node next = cur.next;
            cur.next = node;
            node.next = next;
        }
        return head;
    }
}

Flatten a Multilevel doubly linked list

• 好题

• 建立一个flattenTail函数，return tail node

• 然后分5种情况讨论

  1. head is empty

  2. no child, no next

  3. next, no child

  4. child, no next

  5. child and next

class Solution {
    /*
    1. head is empty
    2. no child, no next
    3. next, no child
    4. child, no next
    5. child and next
    */
    public Node flatten(Node head) {
        flattenTail(head);
        return head;
    }
    
    //return tail node
    private Node flattenTail(Node head) {
        if (head == null) return head; //1
        if (head.child == null) {
            if (head.next == null) { //2
                return head;
            } else {
                return flattenTail(head.next); //3
            }
        } else {
            Node child = head.child;
            Node next = head.next;
            head.child = null;
            Node childTail = flattenTail(child);
            head.next = child;
            child.prev = head;
            if (next != null) { //5
                childTail.next = next;
                next.prev = childTail;
                return flattenTail(next);
            }
            return childTail;
        }
    }
}

LRU Cache

• initial solution

  • doubly linked list + hashmap

  • key is key, value is Node

• follow up, what if only single list is allowed?

  • single list + hashmap

  • key is key, value is prevNode

Doubly list + HashMap

class LRUCache {
    //doubly linked list
    class Node {
        int key;
        int val;
        Node next;
        Node prev;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    Map<Integer, Node> cache;
    int size;
    Node dummyHead, dummyTail;
    
    public LRUCache(int capacity) {
        cache = new HashMap<>(capacity);
        size = capacity;
        dummyHead = new Node(-1, -1);
        dummyTail = new Node(-1, -1);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    //fetch from cache
    //moveFront
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        Node node = cache.get(key);
        moveFront(node);
        return node.val;
    }
    
    //if key exsit, update the value and moveFront
    //else, if cache size exceeds, then removeTail, and then insertFront
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            node.val = value;
            moveFront(node);
            return;
        }
        while (cache.size() >= size) {
            removeTail();
        }
        Node node = new Node(key, value);
        insertFront(node);
        
    }
    //insertFront
    private void insertFront(Node node) {
        //insert between dummy and head
        Node head = dummyHead.next;
        dummyHead.next = node;
        node.prev = dummyHead;
        node.next = head;
        head.prev = node;
        //put into map
        cache.put(node.key, node);
    }
    //moveFront
    private void moveFront(Node node) {
        //connect prev and next
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
        //insert between dummy and head
        Node head = dummyHead.next;
        dummyHead.next = node;
        node.prev = dummyHead;
        node.next = head;
        head.prev = node;
    }
    //removeTail
    private void removeTail() {
        //connect prev and tail
        Node tail = dummyTail.prev;
        Node prev = tail.prev;
        prev.next = dummyTail;
        dummyTail.prev = prev;
        //remove from map
        cache.remove(tail.key);
    }
}

Single list + HashMap

class LRUCache {
    //single linked list
    class Node {
        int key;
        int val;
        Node next;
        //Node prev;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    Map<Integer, Node> cache; //keyToPrev
    int size;
    Node dummyHead, tail;
    //Node dummyTail; no need a dummyTail for single list
    
    public LRUCache(int capacity) {
        cache = new HashMap<>(capacity);
        size = capacity;
        dummyHead = new Node(-1, -1);
        // dummyTail = new Node(-1, -1);
        tail = dummyHead;
        // dummyTail.prev = dummyHead;
    }
    
    //fetch from cache
    //moveToTail
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // Node node = cache.get(key);
        moveToTail(key);
        return tail.val;
    }
    
    //if key exsit, update the value and moveFront
    //else, if cache size exceeds, then removeTail, and then insertFront
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // Node node = cache.get(key);
            moveToTail(key);
            tail.val = value;
        } else {
            //first insert, then removeHead
            insertTail(key, value);
            while (cache.size() > size) {
                removeHead();
            }
            
           
        }
        
        
    }
    //insertTail
    private void insertTail(int key, int val) {
        Node node = new Node(key, val);
        tail.next = node;
        //put into map
        cache.put(key, tail);
        tail = node;
    }
    //moveToTail
    private void moveToTail(int key) {
        //connect prev and next
        Node prev = cache.get(key);
        Node cur = prev.next;
        if (tail == cur) {
            return; //corner case
        }

        prev.next = cur.next;
        tail.next = cur;
        cur.next = null;
        //update in the map
        cache.put(prev.next.key, prev);
        cache.put(key, tail);
        tail = cur;
        
    }
    //removeHead
    private void removeHead() {
        //connect dummyHead and head.next
        Node head = dummyHead.next;
        Node next = head.next;
        dummyHead.next = next;
        //remove head from map
        cache.remove(head.key);
        //re-index
        cache.put(next.key, dummyHead);
    }
}