# Linked List
###### tags: `Study_aboard`
## Delete Nodes
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
return ;
}
};
```
## Palindrome Linked List
```Initial``` Don't know how to do it with $O(1)$ space, maybe recursion or two pointers
```Sol1```
1. we can reverse linked list with $O(n)$ time and $O(1)$ space
2. use two pointer to find the midpoint
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void helper(ListNode* result, ListNode* head)
{
if (!head)
return;
ListNode* tmp = new ListNode( head->val );
tmp->next = result->next;
result->next = tmp;
helper(result, head->next);
}
// reverse
ListNode* reverseList(ListNode* head) {
ListNode * result = new ListNode(0);
helper(result, head);
return result->next;
}
bool isPalindrome(ListNode* head) {
if (!head || !head->next)
return true;
ListNode* index = head;
int count = 0;
// use count to get the midpoint
while (index)
{
count++;
index = index->next;
}
index = head;
for (int i = 0; i < (count-1) / 2; i++)
{
index = index->next;
}
index = reverseList(index->next);
for (int i = 0; i < count / 2; i++)
{
if (index->val != head->val)
return false;
index = index->next;
head = head->next;
}
return true;
}
};
```
```Sol2```
We can use stack in this solution since FILO
==Recursion is implicitly a stack with close to $O(1)$ space==
```cpp
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode *cur = head;
return helper(head, cur);
}
bool helper(ListNode* node, ListNode*& cur) {
if (!node) return true;
bool res = helper(node->next, cur) && (cur->val == node->val);
cur = cur->next;
return res;
}
};
```
## Remove Nth Node From End of List
```cpp
/> n is the length of the linked list
return node1->next;
}
else{
pre->next = node1->next;
return head;
}
}
};
```
## Remove Duplicates from Sorted List I
```cpp
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
ListNode *slow = head, *fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode *last = slow->next, *pre = head;
while (last->next) {
ListNode *tmp = last->next;
last->next = tmp->next;
tmp->next = slow->next;
slow->next = tmp;
}
while (slow->next) {
slow = slow->next;
if (pre->val != slow->val) return false;
pre = pre->next;
}
return true;
}
};
```
## Remove Duplicates from Sorted List II
```Initial```
由於鏈表開頭可能會有重複項，被刪掉的話頭指標會改變，而最終卻還需要返回鏈錶的頭指標，所以需要定義一個新的節點dummy。定義一個前驅指標(pre)和一個現指標(cur)，每當前驅指標指向新建的節點，現指標從下一個位置開始往下遍歷，遇到相同的則繼續往下，直到遇到不同項時，把前驅指標的next指向下面那個不同的元素。 如果現指標遍歷的第一個元素就不相同，則把前驅指標向下移一位。
```Problem```
No problem
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head) return head;
ListNode* cur = head;
ListNode* dummy = new ListNode(-1);
ListNode* pre = dummy;
dummy->next = head;
while(cur){
// we will stay cur!=pre in the whole loop !!!!
if(!cur->next || cur->val != cur->next->val){
pre->next = cur;
pre = cur;
cur = cur->next;
}
else{
while(cur->next && cur->val==cur->next->val){
cur = cur->next;
}
cur = cur->next;
if(!cur) pre->next = cur;
}
}
return dummy->next;
}
};
```
## Reversed Linked List
==Basic but Important==
==Can reverse linked list to get pre pointer==
```Iterative```
Dummy is the new head of the reversed linked list
將 Dummy -> cur -> temp 變成 Dummy -> temp -> cur
，再將temp = cur->next 來做下一次的iterative
```cpp
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head) return head;
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* cur = head;
while(cur->next){
ListNode* temp = cur->next;
cur->next = temp->next;
temp->next = dummy->next; // temp is the last element and should be in the front of linked list
dummy->next = temp;
}
return dummy->next;
}
};
```
```Recursive```
```cpp
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *newHead = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return newHead;
}
};
```
## Reversed linked list II
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
int space;
space = right-left;
ListNode* temp = head;
for(int i=0;i<left-1;i++){
temp = temp->next;
}
while(space>0){
ListNode* temp_end = temp;
for(int i=0;i<space;i++){
temp_end = temp_end->next;
}
int temp_front_val;
temp_front_val = temp->val;
temp->val = temp_end->val;
temp_end->val = temp_front_val;
//cout<<temp->val<<temp_end->val<<endl;
space-=2;
temp = temp->next;
}
return head;
}
};
```
## Odd Even Linked list
```Initial```
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* even_start = head->next;
ListNode* even = head->next;
ListNode* odd = head;
while(odd->next && odd->next->next){
odd->next = odd->next->next;
odd = odd->next;
even->next = even->next->next;
even = even->next;
}
odd->next = even_start;
return head;
}
};
/*
* Time complexity:O(n)
* space: O(1)
* /
```
## Add Two Numbers
Basic but important about how to construct a linked list
1. use new to assign a new address for a linked list node
2. connect next pointer of linked list nodes to form a linked list
3. used to add a dummy node in the front of the linked list
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(-1), *res = dummy;
int carry=0;
while(l1 || l2){
if(!l1){
res->next = new ListNode((l2->val+carry)%10);
carry = (l2->val+carry)/10;
res = res->next;
l2 = l2->next;
continue;
}
if(!l2){
res->next = new ListNode((l1->val+carry)%10);
carry = (l1->val+carry)/10;
res = res->next;
l1 = l1->next;
continue;
}
res->next = new ListNode((l1->val + l2->val + carry)%10);
carry = (l1->val + l2->val + carry)/10;
res=res->next;
l1=l1->next;
l2=l2->next;
}
if (carry) res->next = new ListNode(carry);
return dummy->next;
}
};
```
## Swap Nodes in Pairs
Basic but important
1. Add an additional dummy node to make all situations the same
2. change three pointer directions
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummy = new ListNode(-1), *pre=dummy;
dummy->next = head;
while(pre->next && pre->next->next){
ListNode * temp1 = pre->next;
ListNode* temp2 = pre->next->next;
pre->next = temp2;
temp1->next = temp2->next;
temp2->next = temp1;
pre = pre->next->next;
}
return dummy->next;
}
};
```
## Linked list cycle II
==Good problem==
1. 判斷是否有circle，用一個快指標與一個慢指標，若有，則兩者必定會碰撞
2. 判斷起始點的方式如下
```cpp
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return NULL;
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
};
```
## Merge k linked list ==Microsoft==
1. simplify the answer first -> try to think how to merge two linked list
2. then come to the question -> how to choose the smallest element between k sorted list efficiently
3. Use Min Heap
```cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto cmp = [](ListNode*& a, ListNode*& b) {
return a->val > b->val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp) > q(cmp);
for (auto node : lists) {
if (node) q.push(node);
}
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (!q.empty()) {
auto t = q.top(); q.pop();
cur->next = t;
cur = cur->next;
if (cur->next) // top 的 link list got remain elements
q.push(cur->next);
}
return dummy->next;
}
};
```
## Plus One Linked list
```Sol1```
覺得順序難做，可以先將linked list reverse
```cpp
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
ListNode *rev_head = reverse(head), *cur = rev_head, *pre = cur;
int carry = 1;
while (cur) {
pre = cur;
int t = cur->val + carry;
cur->val = t % 10;
carry = t / 10;
if (carry == 0) break;
cur = cur->next;
}
if (carry) pre->next = new ListNode(1);
return reverse(rev_head);
}
ListNode* reverse(ListNode *head) {
if (!head) return head;
ListNode *dummy = new ListNode(-1), *cur = head;
dummy->next = head;
while (cur->next) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = dummy->next;
dummy->next = t;
}
return dummy->next;
}
};
```
想從底層開始做，想recursive
```cpp
class Solution {
public:
ListNode* plusOne(ListNode* head) {
if (!head) return head;
int carry = helper(head);
if (carry == 1) { // carry can only be 0 or 1
ListNode *res = new ListNode(1);
res->next = head;
return res;
}
return head;
}
int helper(ListNode *node) {
if (!node) return 1; // if null, add 1 to the last element
int carry = helper(node->next);
int sum = node->val + carry;
node->val = sum % 10;
return sum / 10;
}
};
```
## Copy List with Random Pointer ==Google==
[Back to back](https://www.youtube.com/watch?v=OvpKeraoxW0)
==Great problem==
```Sol1```
本題困難點在於traverse linked list 時，要在什麼時候將random pointer 連接上
由於每一個節點都有一個隨機指標，這個指標可以為空，也可以指向鏈表的任意一個節點，如果在每生成一個新節點給其隨機指標賦值時，都要去遍歷原鏈表的話，OJ 上肯定會超時，所以可以考慮用 HashMap 來縮短查找時間
第一遍遍歷生成所有新節點時同時建立一個原節點和新節點的 HashMap， 第二遍給隨機指標賦值時
```cpp
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
Node *res = new Node(head->val, nullptr, nullptr); // new copied list
Node *node = res, *cur = head->next;
unordered_map<Node*, Node*> m; // hashmap old node 與其對應的 new node
m[head] = res;
// first iterate through
while (cur) {
Node *t = new Node(cur->val, nullptr, nullptr);
node->next = t;
m[cur] = t;
node = node->next;
cur = cur->next;
}
// second iteration
node = res; cur = head;
while (cur) {
node->random = m[cur->random]; // old node random 所對應的new node
node = node->next;
cur = cur->next;
}
return res;
}
};
```
Time complexity $O(n)$
Space complexity $O(n)$
```Sol2```
1. First step
==為了將hash map減少掉，但又必須將old node & new node做對應，因此將old node->next 連接到new node==，如此可以少掉hash map的space，但又保留其對應功能
2. Second step
做跟sol1很像步驟，將cur設在old node上，將cur->next->random = cur->random(cur->next即為new node)
3. Third step
將new node的next重新連接好
```cpp
class Solution {
public:
Node* copyRandomList(Node* head) {
if (!head) return nullptr;
Node *cur = head;
// step 1
while (cur) {
Node *t = new Node(cur->val, nullptr, nullptr);
t->next = cur->next;
cur->next = t;
cur = t->next;
}
//step 2: connect random pointer
cur = head;
while (cur) {
if (cur->random) cur->next->random = cur->random->next;
cur = cur->next->next;
}
//step 3: reconstruct next pointer
cur = head;
Node *res = head->next;
while (cur) {
Node *t = cur->next;
cur->next = t->next;
if (t->next) t->next = t->next->next;
cur = cur->next;
}
return res;
}
};
```
## LRU Cache ==Microsoft==
**Good problem**
Read list stl first https://hackmd.io/@chentzj/SkNIsGDpu/Doubled_linked_list#Doubled-linked-list
[BacktoBack](https://www.youtube.com/watch?v=S6IfqDXWa10)
Sol
The problem ask to have **Fast lookups** -> Hashtable can do this
Ask to have **Fast removal** -> double linked list can do this
Combine these two data structures -> A hashmap that stores doubled linked list
```cpp
class LRUCache{
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = m.find(key);
if (it == m.end()) return -1;
l.splice(l.begin(), l, it->second); // it->second is the list
// void splice (iterator position, list& x, iterator i);
// push the val i which is an iterator in x into the position
// move get item to front of the list
return it->second->second;
}
void put(int key, int value) {
auto it = m.find(key);
if (it != m.end()) l.erase(it->second); // if find the item, remove it
l.push_front(make_pair(key, value)); // put item into the front
m[key] = l.begin(); // push the linked list into the map
if (m.size() > cap) {
int k = l.rbegin()->first; // the key of the last link list
l.pop_back(); // pop out the last linked list
m.erase(k); // erase key in map
}
}
private:
int cap;
list<pair<int, int>> l;
unordered_map<int, list<pair<int, int>>::iterator> m;
};
/**
* 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);
*/
```
Sign in with Wallet
Connect another wallet