LinkedList Coding Questions

Notes

单向链表：Singly Linkedlist

从右往左处理： Handle from right to left

(Interview Cake notes)

• Most computers have caching systems that make reading from sequential addresses in memory faster than reading from scattered addresses.
• Array items are always located right next to each other in computer memory, but linked list nodes can be scattered all over. So iterating through a linked list is usually quite a bit slower than iterating through the item in an array, even though they are both theoretically O(n) time.

Common operations:

• Search: O(n)
• Add/Remove: O(1)
• Delete a node from a singly linkedlist

Given a node n, we find the previous node prev and set prev.next equal to n.next. If the list is doubly linked, we must also update n.next to set n.next.prev equal to n.prev.

Remember to check for the null pointer and to update the head or tail pointer as needed.

One thing to note that we ALWAYS check if the given node is of length 0 or 1. if(head==null || head.next==null) return head;

Techniques:

• Runner Technique

You iterate through the linked list with two pointers simultaneously, with one ahead of the other.

For example, suppose you had a linked list a1 ->a2 -> ••• ->an ->b1 ->b2 -> ••• ->bn and you wanted to rearrange it into a1 ->b1 ->a2 ->b2 -> ••• ->an ->bn. You do not know the length of the linked list (but you do know that the length is an even number).

You can have the fastPointer move every 2 elements for every 1 move that the slowPointer makes. When fastPointer hits the end of the linked list, the slowPointer will be at the midpoint. Then, move the fastPointer back to the front and begin “weaving”the elements. On each iteration, slowPointer selects an element and inserts it after fastPointer.

• Recursion

Syntax

LinkedList<Integer> ll = new LinkedList<Integer>();

Questions (From Cracking the Coding interview)

1. Write code to remove duplicated from an unsorted Linked List.

(Simple solution)

Use a simple HashMap to track duplicates.

HashSet<Integer> set = new HashSet<>();

(more complex solution without the need for extra storage):

Imagine each item in the array as a node in a linked list. In any linked list, ↴ each node has a value and a “next” pointer. In this case:

• The value is the integer from the array.
• The “next” pointer points to the value-eth node in the list (numbered starting from 1). For example, if our value was 3, the “next” node would be the third node.

The first thing we should do is to think of what happens when we have duplicates? If duplicates occurs, a single node would have two incoming arrows. Two nodes will point to the same node.

So if we can find a node that has more than 1 incoming pointers, then it must be a duplicate. The next issue is, how do we find such a node?

Pattern 1: The last node often does not have any incoming pointers.

Pattern 2: There is always a cycle since each node either points to itself or another node.

If we walk through our linked list, starting from the head, at some point we will enter our cycle. Try tracing that path on the example lists below. Notice anything special about the first node we hit when we enter the cycle?

The first node in the cycle always has at least two incoming pointers!

To find this first node, we know that we can have a pointer at position X and another pointer at position X+Y where Y is the length of the cycle. Both will then be pointing to the same node and we know that this is the first node.

So, how do we find the length of the cycle?

If we can get inside the cycle, we can just remember a position and count how many steps it takes to get back to that position.

So how to get inside this circle?

Well, there has to be a cycle in our list, and at the latest, the cycle is just the last node we hit as we traverse the list from the head:

So we can just start at the head and walk n steps. By then we’ll have to be inside a cycle.

The overall strategy is here…(to see more, can refer to either the TB or interview Cake)

1. We know the position of a node with multiple incoming pointers is a duplicate in our array because the nodes that pointed to it must have the same value.
2. We find a node with multiple incoming pointers by finding the first node in a cycle.
3. We find the first node in a cycle by finding the length of the cycle and advancing two pointers: one starting at the head of the linked list, and the other starting ahead as many steps as there are steps in the cycle. The pointers will meet at the first node in the cycle.
4. We find the length of a cycle by remembering a position inside the cycle and counting the number of steps it takes to get back to that position.
5. We get inside a cycle by starting at the head and walking n steps. We know the head of the list is at position n+1.

This is hands-down a very intense question. Phew.

2. Return Kth to Last

Implement an algorithm to find the kth element to the last element in the list.

Solution: Just use 2 pointers and put them k nodes apart. Traverse both at the same pace until the further pointer reaches last element in the list.

3. Delete Middle Node

Implement an algorithm to delete a node that can be anywhere in the list except first and last node, given only access to that node. Singly linked list is used.

Solution:

Node nextNode = nodeToDelete.next;

nodeToDelete.value = nextNode.value;

nodeToDelete.next = nextNode.next;

edge cases: nodeToDelete==null || nodeToDelete.next==null

4. Sum Lists

You are given two numbers represented by a linked list….

I have done this question countless times but i still havent’t been able to master it.

Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is,617 + 295.
Output: 2 -> 1 -> 9. That is, 912.\

There isn’t any need for reassignment of next node etc. Just create a new ListNode with the nextNode being the return value of the recursive function to be called.

(Extension, LeetCode 445)

Now, the given linked lists are not reversed.

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

A solution that i wrote -> It doesn’t use a stack. Much better than I first wrote it.

We will first add the preceding 0s to the Listnodes as necessary. When we perform the recursion, we will be sure that both lists have the same length. The recursion will keep continuing until we have reached the last node of both lists. From there, the computation will happen and the output of that last function stack will return a list node — representing the last digit of the final answer. The carryOver value, which is a global variable, will be modified accordingly.

Upon returning to the previous function stack, at the second last nodes of both list,, we will once again do the computation and set next nodes correctly. This repeats until all the function stacks are returned.

5. Palindrome

Go to the tail end and the head. Then traverse them.

6. Intersection

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.

How do we detect if two LL intersects?

• One approach would be to use a hash set and just throw all the linked list nodes inside.
• Another approach is to observe that two intersecting LL will have the same last node. Thus, we can just traverse to the end of each LL and compare the last nodes.

How to find intersecting nodes?

• We can traverse backwards through each LL. When the LL split, that’s the intersection.
• Run through each LL to get the lengths and the tails
• Compare the tails. If they are different (by reference not values), return immediately. There is no intersection.
• Set 2 pointers to the start of each LL.
• On the longer Linked List, advance its’ pointer by the differences in length.
• Now, traverse on each LL until the pointers are the same.

7. Loop Detection

Given a circular linked list, implement an algorithm that returns the node at the beginning of the loop.

EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

Questions (From Interview Cake)

1. Delete a node from a singly-linked list, given only a variable pointing to that node.

We’d change the previous node’s pointer to skip the node we want to delete, so it just points straight to the node after it.

So we need a way to skip over the current node and go straight to the next node. But we don’t even have access to the previous node!

Since we can only access forward (nodes that are after the node to be deleted), one solution is:

We take value and next from the input node’s next node and copy them into the input node. Now the input node’s previous node effectively skips the input node’s old value!

public static void deleteNode(LinkedListNode nodeToDelete) {

    // get the input node's next node, the one we want to skip to
    LinkedListNode nextNode = nodeToDelete.next;

    if (nextNode != null) {

        // replace the input node's value and pointer with the next
        // node's value and pointer. the previous node now effectively
        // skips over the input node
        nodeToDelete.value = nextNode.value;
        nodeToDelete.next  = nextNode.next;

    } else {

        // eep, we're trying to delete the last node!
        throw new IllegalArgumentException("Can't delete the last node with this technique!");
    }
}

*** There are problems with this implementation for the last node. ***

Problem 1: We could change the node we’re deleting to have a value of null, but the second-to-last node’s next pointer would still point to a node, even though it should be null. Unless we are fine with lazy deletion.

LinkedListNode a = new LinkedListNode(3);
LinkedListNode b = new LinkedListNode(8);
LinkedListNode c = new LinkedListNode(2);

a.next = b;
b.next = c;

deleteNode(b);

Problem 2: Any references to the input node have now effectively been reassigned to its next node. In our example, we “deleted” the node assigned to the variable b, but in actuality we just gave it a new value (2) and a new next! If we had another pointer to b somewhere else in our code and we were assuming it still had its old value (8), that could cause bugs.

Problem 3: If there are pointers to the input node’s original next node, those pointers now point to a “dangling” node (a node that’s no longer reachable by walking down our list). In our example above, c is now dangling. If we changed c, we’d never encounter that new value by walking down our list from the head to the tail.

Questions (From Leet Code)

1. Odd Even Linked List (328)

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number by order and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

The idea is to create 2 different lists to store the values in the odd or even positions, then combine them at the end and return the head of this new combined list.

Step 1:

Step 2:

Step 3:

Step 4:

Step 5:

Step 6:

At the last step, we need to make sure that evenTail and oddTail are all pointing to a null. This is important because if we did not do it (in this case, for example, evenTail), we see that evenTail.next is oddTail instead of null. We will find that there is a cycle in the linked list when we combine evenHead list (purple) with oddHead list (green).

2. Next Greater Node in LL (1019)

We are given a linked list with head as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

Input: [2,1,5]
Output: [5,5,0]

Example 2:

Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

Hint: We can use a stack that stores nodes in monotone decreasing order of value. When we see a node_j with a larger value, every node_i in the stack has next_larger(node_i) = node_j .

tracker.add and tracker.push is the same…

1. The Data Structures that we use here: Stack (To keep track of the biggest number for the current number that we are iterating through) and int array called Big (To be returned as the answer)
2. First, we add the last element into the Stack since we know that no other elements are greater than it.
3. As we begin traversing from the rightmost to the leftmost, we store the current value in the variable called current. We compare the current value with the values inside the stack.
4. In the code above, we have a while loop which makes sure that stack.peek() will contain a value that is greater than current value. Afterwards, the stack will either be popped finished to become empty or still contain an element. Whether it is empty or not, we will add the current value into the stack. If it is empty, we will do the action of setting Big value for this current value to be 0. If it is not empty, we will set Big value to be stack.peek() value.
5. Overall, we will have the following two cases:

• Case 1: current value < stack.peek(), then we just initialise Big int array at this current position to be stack.peek()
• Case 2: current value ≥ stack.peek(), then we do stack.pop() repeatedly until we reach case 1. If the stack becomes empty by then, then we just set Big int array at this current position = 0 and do stack.push(current).

3. Swap Nodes in Pairs (24)

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3

Recursion is easier.

4. Remove Nth Node From End of List (19)

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

Example:

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Comment for line 22: n nodes away means n+1 skips

3 would be n+1. Note that in the code, we have count=0 at the start instead of 1.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {

        int len = 0;
        ListNode head1 = head;
        while(head1!=null){
            head1=head1.next;
            len++;
        }

        int positionToRemove = len-n;
        if(positionToRemove == 0){
            return head.next;
        }

        int i=0;
        ListNode rightBefore = head;
        while(i<(positionToRemove-1)){
            rightBefore=rightBefore.next;
            i++;
        }

        

        ListNode nodeToRemove = rightBefore.next;
        if (nodeToRemove.next != null){
            ListNode remaining = nodeToRemove.next;
            rightBefore.next = remaining;
        } else {
            rightBefore.next = null;
        }

        return head;
    
    }
}

5. Reverse Linked List II (92)

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Need to define Comparator for Priority Queue.

Leet Code 25 Reverse Nodes in K-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

Follow up:

• Could you solve the problem in O(1) extra memory space?
• You may not alter the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Example 3:

Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]

Example 4:

Input: head = [1], k = 1
Output: [1]

// Another attempt in 2023

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode headCopy = head;
        int count = 0;
        while(headCopy!= null && count<k){
            headCopy = headCopy.next;
            count++;
        }

        if(headCopy == null && count < k) return head;

        // can reverse
        ListNode remaining = reverseKGroup(headCopy, k);
        int count2 = 0;
        while(head!=null && count2 < k){
            ListNode newHead = head.next;
            head.next = remaining;
            remaining = head;
            head = newHead;
            count2++;
        }

        return remaining;

    }
}

148. Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

If we want to sort it in O(NLogN) time.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode mid = getMid(head);
        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        return merge(left, right);
    }

    ListNode merge(ListNode list1, ListNode list2){
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
        }

        tail.next = (list1 != null) ? list1 : list2;
        return dummyHead.next;
    }

    ListNode getMid(ListNode head){
        ListNode midPrev = null;
        ListNode fast = head;
        ListNode slow = head;

        while(fast != null && fast.next!=null){
            fast = fast.next.next;
            midPrev = slow;
            slow = slow.next;
        }
        midPrev.next = null; // impt..need to separate head to midPrev and mid...
        return slow;
    }
}

163. Missing Ranges

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are within the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the shortest sorted list of ranges that exactly covers all the missing numbers. That is, no element of nums is included in any of the ranges, and each missing number is covered by one of the ranges.

Example 1:

Input: nums = [0,1,3,50,75], lower = 0, upper = 99
Output: [[2,2],[4,49],[51,74],[76,99]]
Explanation: The ranges are:
[2,2]
[4,49]
[51,74]
[76,99]

Example 2:

Input: nums = [-1], lower = -1, upper = -1
Output: []
Explanation: There are no missing ranges since there are no missing numbers.

Other people’s solution

List<String> res = new ArrayList<String>();
  
  // the next number we need to find
  int next = lo;
  
  for (int i = 0; i < a.length; i++) {
    // not within the range yet
    if (a[i] < next) continue;
    
    // continue to find the next one
    if (a[i] == next) {
      next++;
      continue;
    }
    
    // get the missing range string format
    res.add(getRange(next, a[i] - 1));
    
    // now we need to find the next number
    next = a[i] + 1;
  }
  
  // do a final check
  if (next <= hi) res.add(getRange(next, hi));

  return res;

String getRange(int n1, int n2) {
  return (n1 == n2) ? String.valueOf(n1) : String.format("%d->%d", n1, n2);
}

My attempt after some correction

class Solution {
    public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper) {
        List<List<Integer>> result = new LinkedList<>();
        int i=lower;
        int numsIndex=0;
        // i is the number we check between lower and upper
        // numsIndex is an index of nums arr
        while(i<=upper && numsIndex<nums.length){
            if(nums[numsIndex] > i){
                result.add(Arrays.asList(i, nums[numsIndex]-1));
                i=nums[numsIndex] + 1;
                numsIndex++;
            } else if(nums[numsIndex] == i) {
                i=nums[numsIndex] + 1; // or i++;
            } else{
                numsIndex++; // can skip this value in nums since previous nums already covers
            }
        }
        if(i<=upper){
            result.add(Arrays.asList(i, upper));
        }
        return result;
    }
}

146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

First approach

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Second approach

class LRUCache {
    Map<Integer, Node> map;
    LinkedNodeList list;
    Integer capacity;
    public LRUCache(int capacity) {
        this.list = new LinkedNodeList();
        this.map = new HashMap(capacity);
        this.capacity=capacity;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if(node == null) return -1;
        list.moveToHead(node); // indicate most recently used
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if(node != null){
            list.moveToHead(node);
            node.value=value; 
        } else {
            // consider to trim when we need to add new node
            Node newNode = new Node(key, value);
            if(map.size() == capacity){
                Node tail = list.getTail();
                map.remove(tail.key); // remove last node from map
                list.removeTail(); // remove last node from list
            }
            map.put(key, newNode);
            list.addToHead(newNode);
        }
    }
}

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

class LinkedNodeList{
    Node dummyHead;
    Node dummyTail;

    LinkedNodeList(){
        dummyHead = new Node(0,0); // create dummy nodes so we don't deal with null
        dummyTail = new Node(0,0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    void moveToHead(Node node){
        // remove node from being attached to it's prev and next
        node.prev.next=node.next;
        node.next.prev=node.prev;
        addToHead(node);
    }

    void addToHead(Node node){
        Node tmp = dummyHead.next;
        dummyHead.next=node;
        node.next=tmp;

        tmp.prev=node;
        node.prev=dummyHead;
    }

    void removeTail(){
        Node tmp = dummyTail.prev.prev;
        tmp.next=dummyTail;
        dummyTail.prev=tmp;
    }

    Node getTail(){
        return dummyTail.prev;
    }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

61. Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;

        // make the list into a ring
        ListNode oldTail = head;
        int len = 1;
        while(oldTail.next != null){
            len++;
            oldTail = oldTail.next;
        }
        oldTail.next = head;

        ListNode newTail = head;
        int i=0;
        while(i < (len - (k % len)) - 1){
            newTail = newTail.next;
            i++;
        }

        ListNode newHead = newTail.next;

        // break the ring
        newTail.next = null;
        return newHead;
    }
}

Make the given list into a circular list.

138. Copy List with Random Pointer

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Solution from Editorial

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
public class Solution {
  // HashMap which holds old nodes as keys and new nodes as its values.
  HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();

  public Node copyRandomList(Node head) {

    if (head == null) {
      return null;
    }

    // If we have already processed the current node, then we simply return the cloned version of
    // it.
    if (this.visitedHash.containsKey(head)) {
      return this.visitedHash.get(head);
    }

    // Create a new node with the value same as old node. (i.e. copy the node)
    Node node = new Node(head.val, null, null);

    // Save this value in the hash map. This is needed since there might be
    // loops during traversal due to randomness of random pointers and this would help us avoid
    // them.
    this.visitedHash.put(head, node);

    // Recursively copy the remaining linked list starting once from the next pointer and then from
    // the random pointer.
    // Thus we have two independent recursive calls.
    // Finally we update the next and random pointers for the new node created.
    node.next = this.copyRandomList(head.next);
    node.random = this.copyRandomList(head.random);

    return node;
  }
}

133. Clone Graph

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

Test case format:

For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Example 1:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Constraints:

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    HashMap<Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        if(node == null) return null;
        if(visited.containsKey(node)) return visited.get(node);
        
        Node newNode = new Node(node.val);
        visited.put(node, newNode);

        ArrayList<Node> newNeigh = new ArrayList<>();
        for(Node neigh: node.neighbors){
            newNeigh.add(cloneGraph(neigh));
        }
        newNode.neighbors = newNeigh;

        return newNode;
    }   
}

Same technique as the question in 138.

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

A critical point in a linked list is defined as either a local maxima or a local minima.

A node is a local maxima if the current node has a value strictly greater than the previous node and the next node.

A node is a local minima if the current node has a value strictly smaller than the previous node and the next node.

Note that a node can only be a local maxima/minima if there exists both a previous node and a next node.

Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].

Example 1:

Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].

Example 2:

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

Example 3:

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:
- [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.

Constraints:

• The number of nodes in the list is in the range [2, 105].
• 1 <= Node.val <= 105

My messy solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        if(head == null){
            return new int[]{-1, -1};
        }
        int firstCritical = 1000000;
        int lastCritical = -1;
        int previousVal = head.val;
        int previousCritical = -1;
        int minimumDis = 1000000;

        int count = 1;
        head = head.next;
        while(head != null){
            int currVal = head.val;
            if(head.next == null){
                break;
            }
            boolean isCritical = checkCritical(currVal, previousVal, head.next.val);
            previousVal = currVal;
            head = head.next;
            if(!isCritical) {
                count++;
                continue;
            }
            if(previousCritical != -1){
                minimumDis = Math.min(minimumDis, count-previousCritical);
            }
            
            firstCritical = Math.min(firstCritical, count);
            lastCritical = count;
            previousCritical = count;
            count++;
        }
        if(firstCritical == lastCritical || firstCritical == 1000000 || lastCritical == -1 || minimumDis == 1000000){
            return new int[]{-1, -1};
        }
        return new int[]{minimumDis, lastCritical-firstCritical};
    }

    private boolean checkCritical(int val1, int val2, int val3){
        return (val1 > val2 && val1 > val3) || (val1 < val2 && val1 < val3);
    }
}

The end for now :)