Category Archives: List

LRU Cache

Posted on by
Reply

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Solution: Use a doubly linked list, with a head and tail node pointers, as well as a hashMap with all the key and node pairs.

1. When get(), it first checks if the key is in the map, if it is, remove that node from its original position and move to the tail (right before the tail node). if it doesn’t exists, return -1.

2. When set(key, value), it first call get function, to see if it exists, them update the value, otherwise, check if the queue is full, then remove the first element (the one right after head node) and add the new node to the tail.

Set(), Get() O(1) Time.

public class Solution {
    public class Node {
        int key;
        int value;
        Node prev;
        Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    Map<Integer, Node> cache;
    int capacity;
    Node head;
    Node tail;

    public Solution(int capacity) {
        cache = new HashMap<>();
        this.capacity = capacity;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (cache.containsKey(key)) {
            //remove it from its original place
            //put to the tail the queue
            Node node = cache.get(key);
            removeNode(node);
            addToTail(node);
            return node.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (get(key) != -1) {
            cache.get(key).value = value;
            return;
        }
        Node newNode = new Node(key, value);
        if (cache.size() < capacity) {
            addToTail(newNode);
        } else {
            cache.remove(head.next.key);
            removeNode(head.next);
            addToTail(newNode);
        }
        cache.put(newNode.key, newNode);
    }

    public void addToTail(Node node) {
        node.prev = tail.prev;
        node.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }

    public void removeNode(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        node.next = null;
        node.prev = null;
    }
}

 

FacebookTwitterGoogle+Share

Linked List Cycle I & II

Posted on by
Reply

Linked List Cycle I 问有没有环

Given a linked list, determine if it has a cycle in it.

Challenge

Follow up:
Can you solve it without using extra space?

Example

Given -21->10->4->5, tail connects to node index 1, return true

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

Linked List Cycle II 问环的入口

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，返回10

Challenge

Follow up:
Can you solve it without using extra space?

Solution: 当在找环的过程中slow和fast相遇后，第一题直接return true就行了，这题需要找到环的入口。从slow.next到环的入口的距离等于从head到环的入口的距离。

public ListNode detectCycle(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null && slow != fast) {
        slow = slow.next;
        fast = fast.next.next;
    }
    if (fast == null || fast.next == null) {
        return null;
    }
    ListNode runner = head;
    while (runner != slow.next) {
        runner = runner.next;
        slow = slow.next;
    }
    return runner;
}

Reorder List

Posted on by
Reply

Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

Solution: O(n) time and O(1) extra space

Steps:

1. find middle of linked list

2. reverse from mid.next to end as right list

3. Merge left list(from head to mid) and right list(end to mid.next)

public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode mid = findMiddle(head);
    ListNode right = mid.next;
    right = reverse(right);
    mid.next = null;
    ListNode left = head;
    ListNode dummyHead = new ListNode(0);
    ListNode runner = dummyHead;
    int count = 0;
    while (left != null && right != null) {
        if (count % 2 == 0) {
            runner.next = left;
            left = left.next;
        } else {
            runner.next = right;
            right = right.next;
        }
        count++;
        runner = runner.next;
    }
    if (left != null) {
        runner.next = left;
    } else {
        runner.next = right;
    }
    head = dummyHead.next;
}

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

public ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Copy List with Random Pointer

Posted on by
Reply

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Challenge

Could you solve it with O(1) space?

Solution1: O(n) space, using HashMap put save (node, new node) pairs

public RandomListNode copyRandomList(RandomListNode head) {
    //O(n) space version, using hashMap
    if (head == null) {
        return null;
    }
    Map<RandomListNode, RandomListNode> map = new HashMap<>();
    RandomListNode runner = head;
    RandomListNode headCopy = new RandomListNode(head.label);
    map.put(head, headCopy);
    RandomListNode copyRunner = headCopy;
    //deep copy nodes and next pointers
    while (runner.next != null) {
        copyRunner.next = new RandomListNode(runner.next.label);
        runner = runner.next;
        copyRunner = copyRunner.next;
        map.put(runner, copyRunner);
    }
    //deep copy random pointers
    for (RandomListNode node : map.keySet()) {
        map.get(node).random = map.get(node.random);
    }
    return headCopy;
}

Solution2: O(1) space

Convert Sorted List to Binary Search Tree

Posted on by
Reply

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

 

Solution:

1. 找到midNode，这个就是root node

2. 两边建树 分别加到这个root的left, right

注意左右字数可能为null的情况 以及midNode可能为head的情况

public TreeNode sortedListToBST(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode mid = findMiddle(head);
    TreeNode root = new TreeNode(mid.val);
    ListNode midPost = mid.next;
    if (mid != head) {
        root.left = sortedListToBST(head);
    }
    root.right = sortedListToBST(midPost);

    return root;

}

public ListNode findMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    ListNode pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    //Remember to set pre.next = null
    if (pre != null) {
        pre.next = null;
    }
    return slow;
}

Remove Nth Node From End of List

Posted on by
Reply

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

Example

Given linked list: 1->2->3->4->5->null, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5->null.
Note

The minimum number of nodes in list is n.

Challenge

O(n) time

Solution: One Pass using Fast Slow Pointers

O(n) time, O(1) space

ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) {
        return null;
    }
    ListNode slow = head;
    ListNode fast = slow;
    for (int i = 0; i < n; i++) {
        if (fast.next == null) {
            return head.next;
        }
        fast = fast.next;
    }
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return head;
}

 

Sort List

Posted on by
Reply

Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example

Given 1-3->2->null, sort it to 1->2->3->null.

Solution: O(nlogn) time. logn layer, each layer takes O(n) time to merge and O(n) time to find middle

像mergesort的思路:

1.找中点(findMiddle)

2.两边各自sort

3.Merge

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

public ListNode merge(ListNode node1, ListNode node2) {
    ListNode dummyHead = new ListNode(0);
    ListNode runner = dummyHead;
    while (node1 != null && node2 != null) {
        if (node1.val < node2.val) {
            runner.next = node1;
            node1 = node1.next;
        } else {
            runner.next = node2;
            node2 = node2.next;
        }
        runner = runner.next;
    }
    if (node1 != null) {
        runner.next = node1;
    } else {
        runner.next = node2;
    }
    return dummyHead.next;
}


public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) { // check head.next is important
        return head;
    }
    ListNode mid = findMiddle(head);
    ListNode midPost = mid.next;
    mid.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(midPost);

    return merge(left, right);
}

Reverse Linked List I & II

Posted on by
Reply

Reverse Linked List I

Reverse a linked list.

Example

For linked list 1->2->3, the reversed linked list is 3->2->1

Challenge

Reverse it in-place and in one-pass

Solution: In-place and one-pass

public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(0);
    ListNode runner = head;
    while (runner != null) {
        ListNode next = runner.next;
        runner.next = dummyHead.next;
        dummyHead.next = runner;
        runner = next;
    }
    return dummyHead.next;
}

Reverse Linked List II

Reverse a linked list from position m to n.

Example

Given 1->2->3->4->5->NULL, m = 2 and n = 4, return 1->4->3->2->5->NULL.

Note

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Challenge

Reverse it in-place and in one-pass

public ListNode reverseBetween(ListNode head, int m , int n) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(0);
    dummyHead.next = head;
    ListNode runner = dummyHead;
    for (int i = 1; i < m; i++) {
        runner = runner.next;
    }
    ListNode preNode = runner;
    ListNode mNode = runner.next;
    ListNode nNode = mNode;
    ListNode postnNode = nNode.next;
    ListNode dummy = new ListNode(0);
    for (int i = m; i < n; i++) {
        ListNode temp = postnNode.next;
        postnNode.next = nNode;
        nNode = postnNode;
        postnNode = temp;
    }
    mNode.next = postnNode;
    preNode.next = nNode;
    return dummyHead.next;

}

Remove Duplicates from Sorted List I && II

Posted on by
Reply

Remove Duplicates from Sorted List I

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example

Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

public static ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode runner = head;
    while (runner.next != null) {
        if (runner.next.val == runner.val) {
            runner.next = runner.next.next;
        } else {
            runner = runner.next;
        }
    }
    return head;
}

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

    public static ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }   
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode runner = dummyHead;
        int preValue = dummyHead.val;
        while(runner.next!=null){
            if(runner.next.val==preValue || 
            (runner.next.next!=null && runner.next.next.val == runner.next.val)){
                preValue = runner.next.val;//keep track of the previous value
                runner.next = runner.next.next;//delete runner.next
            }else{
                preValue = runner.next.val;
                runner = runner.next;//keep moving forward
            }
        }
        return dummyHead.next;
    }

Partition List

Posted on by
Reply

Lintcode Online Judge

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2->null and x = 3,
return 1->2->2->4->3->5->null.

    public ListNode partition(ListNode head, int x) {
        ListNode leftDummy = new ListNode(0);
        ListNode left = leftDummy;
        ListNode rightDummy = new ListNode(0);
        ListNode right = rightDummy;
        while(head!=null){
            if(head.val<x){
                left.next = head;
                left = left.next;
            }else{
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        right.next = null; //important
        left.next = rightDummy.next;
        
        return leftDummy.next;
    }