# 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);
    }
}

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/2_linked_list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.