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

- 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. - We find a
**node with multiple incoming pointers**by finding the first node in a cycle. - 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. - 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. - 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 intersecting 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 .

- 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) - First, we add the last element into the Stack since we know that no other elements are greater than it.
- 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.
- 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. - 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.After removing the second node from the end, the linked list becomesn= 21->2->3->5.

`/**`

* 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.