# 2. Linked List

## 好题

* [Remove duplicates from sorted list II](https://app.gitbook.com/@yu-sun/s/leetcode/~/drafts/-MC4I2K9Qea4BRk7w38z/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);
    }
}

```