# Linked List topic
# 19. Remove Nth Node From End of List
## Question: (Medium)
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Example 2:
Input: head = [1], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 1
Output: [1]
## Solution: C++
```c=
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* first = head;
ListNode* second = head;
ListNode* prev = NULL;
while(n--){
second = second->next;
}
if(second==NULL)
return head->next;
while(second!=NULL){
prev = first;
first = first->next;
second = second->next;
}
if(prev==NULL)
return NULL;
else
prev->next = first->next;
return head;
}
};
```
## Notes:
1. two-pointer，first ptr & second ptr
2. second ptr**事先往前走n步**
3. 當second ptr為null時，first ptr就剛好是你要移除的Node。
---
# 206. Reverse Linked List
## Question: (Easy)
Given the head of a singly linked list, reverse the list, and return the reversed list.
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
## Solution: C++
```c=
/**
* 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* reverseList(ListNode* head) {
ListNode* next = NULL;
ListNode* prev = NULL;
while(head!=NULL){
next = head->next;
head->next = prev;
prev = head;
if(next==NULL)
break;
head = next;
}
return head;
}
};
```
## Notes:
1. 建立兩個主要的變數，prev、next ptr，即可完成這題
---
# 21. Merge Two Sorted Lists
## Question: (Easy)
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
## Solution ("C")
```c=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* root = (struct ListNode*)malloc(sizeof(struct ListNode));
root->val = 0;
root->next = NULL;
struct ListNode* ans = root;
while(list1!=NULL && list2!=NULL){
if(list1->val <= list2->val){
root->next = list1;
list1 = list1->next;
}
else{
root->next = list2;
list2 = list2->next;
}
root = root->next;
}
if(list1==NULL&&list2!=NULL){
root->next = list2;
}
else if(list1!=NULL&&list2==NULL){
root->next = list1;
}
return ans->next;
}
```
## Notes:
* 用two-pointer，若小於對方，則往前走
---
# 143. Reorder List
## Question(Medium)
You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
## Solution ("C")
```c=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
void reorderList(struct ListNode* head){
struct ListNode* list1;
struct ListNode* list2;
struct ListNode* prev = NULL;
struct ListNode* fast = head;
list1 = head;
while(head!=NULL&&fast!=NULL){
prev = head;
head = head->next;
if(fast->next==NULL)
break;
fast = fast->next->next;
}
prev->next = NULL;
list2 = head;
struct ListNode* next = NULL;
prev = NULL;
//reverse list2
while(list2!=NULL){
next = list2->next;
list2->next = prev;
prev = list2;
if(next==NULL)
break;
list2 = next;
}
// combine list1 and list2
int count = 0;
struct ListNode* ans = list1;
list1 = list1->next;
while(list1!=NULL && list2!=NULL){
if(count%2==0){
ans->next = list2;
list2 = list2->next;
}
else{
ans->next = list1;
list1 = list1->next;
}
ans = ans->next;
count++;
}
if(list1==NULL&&list2!=NULL){
ans->next = list2;
}
else if(list1!=NULL&&list2==NULL){
ans->next = list1;
}
}
```
## Notes:
1. 先找出middle node (list1)
2. 將middle node後的linked list做reverse (list2)
3. 合併 list1 & list2
---
# 141. Linked List Cycle
## Question
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
## Solution (C++)
```c=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow==fast){
return true;
}
}
return false;
}
};
```
## Notes:
* 用two-pointer method
* slow ptr & fast ptr，slow每次往前一步，fast每次往前兩步
* 當slow=fast時，表示有cycle發生
---
# 142. Linked List Cycle II
## Question
Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.
## Solution (C++)
```c=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
ListNode* temp = NULL;
if(head==NULL || head->next==NULL)
return NULL;
while(fast!=NULL && fast->next!=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow==fast){
cout<<"cycle "<<slow->val<<endl;
temp = slow;
break;
}
}
while(temp!=NULL){
if(head==temp){
return head;
}
head = head->next;
temp = temp->next;
}
return NULL;
}
};
```
## Notes:
* 沒時間理解原理，目前先用記解法的方式。
* 先判斷是否有cycle，將相遇的node紀錄起來。
* 再跑一次迴圈，分別從head和相遇的點開始做iteration，若又相遇了，該點則為cycle發生的node。
---
# 707. Design Linked List
## Question (Medium)
Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.
Implement the MyLinkedList class:
MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.
Example 1:
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]
Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
myLinkedList.get(1); // return 2
myLinkedList.deleteAtIndex(1); // now the linked list is 1->3
myLinkedList.get(1); // return 3
## Solution (C++)
```c=
class MyLinkedList {
struct ListNode{
int val;
ListNode* next;
ListNode(int value){
val = value;
next = NULL;
}
};
private:
int size;
public:
ListNode* root;
MyLinkedList() {
root = NULL;
size = 0;
}
void show(ListNode* root){
cout<<"show = ";
while(root!=NULL){
cout<<root->val<<" ";
root = root->next;
}
cout<<endl;
}
int get(int index) {
if(root==NULL || index>=size)
return -1;
ListNode* temp = root;
for(int i=0; i<index; i++){
temp = temp->next;
}
return temp->val;
}
void addAtHead(int val) {
ListNode* newNode = new ListNode(val);
newNode->next = root;
root = newNode;
cout<<root->val<<endl;
size++;
}
void addAtTail(int val) {
ListNode* newNode = new ListNode(val);
ListNode* temp = root;
if(root==NULL){
root = newNode;
size++;
return;
}
while(temp->next!=NULL)
temp = temp->next;
temp->next = newNode;
size++;
}
void addAtIndex(int index, int val) {
index = (index<0)?0:index;
if(index>size)
return;
ListNode* newNode = new ListNode(val);
if(index==0){
newNode->next = root;
root = newNode;
size++;
return;
}
ListNode* temp = root;
ListNode* next_ptr = temp->next;
for(int i=0; i<index-1; i++){
temp = temp->next;
next_ptr = temp->next;
}
temp->next = newNode;
newNode->next = next_ptr;
size++;
}
void deleteAtIndex(int index) {
if(index>=size)
return;
ListNode* temp = root;
ListNode* prev = NULL;
for(int i=0; i<index; i++){
prev = temp;
temp = temp->next;
}
if(prev==NULL)
root = temp->next;
else{
if(temp==NULL)
prev->next = NULL;
else
prev->next = temp->next;
}
size--;
//free(temp);
}
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
*/
```
## Notes:
* 建議大家別寫，題目沒有說明很清楚。
* 問題不難，但testcase會有很多**邊界的case要考慮**
## 1721. Swapping Nodes in a 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* swapNodes(ListNode* head, int k) {
ListNode* root = head;
ListNode* node1 = NULL;
ListNode* node2 = NULL;
ListNode* temp = head;
int count = 1;
for(int i=0; i<k; i++){
if(temp!=NULL)
temp = temp->next;
}
while(head!=NULL){
if(count==k){
node1 = head;
}
if(node2==NULL){
if(temp == NULL){
node2 = head;
}
if(temp!=NULL)
temp = temp->next;
}
head = head->next;
count++;
if(node1!=NULL && node2!=NULL)
break;
}
int t = node1->val;
node1->val = node2->val;
node2->val = t;
return root;
}
};
```
### Notes:
1. 這題其實只要找出兩個要swap的node即可，swap只需要對**數值**即可通過。
(若是要整個node交換，這題會變很麻煩)
3. 由前往後的第k個node: 一直往前遍歷，並用count紀錄目前是第幾個node。
4. 由後往前的第k個node: 先設定一個pointer temp，**先往前走k步**，接著從頭開始遍歷，當temp == NULL時，head就代表倒數第k個node。
---
## 1171. Remove Zero Sum Consecutive Nodes from Linked List
```c++=
/**
* 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* removeZeroSumSublists(ListNode* head) {
ListNode* temp = new ListNode(0, head);
ListNode* ans = temp;
int prefix = 0;
map<int, ListNode*> mapping;
while(temp!=NULL){
prefix = prefix + temp->val;
//check prefix exist?
if(mapping.find(prefix)!=mapping.end()){
ListNode* t = mapping[prefix]->next;
int temp_prefix = prefix + t->val;
while(t!=temp){
mapping.erase(temp_prefix);
t = t->next;
temp_prefix = temp_prefix + t->val;
}
mapping[prefix]->next = temp->next;
}
else{
mapping[prefix] = temp;
}
temp = temp->next;
}
return ans->next;
}
};
```
### Notes:
1. prefix sum，由左到右，如果發現這個node prefix sum在前面有出現過，代表這中間的node都可以刪掉了
2. 核心概念: map<int, ListNode*>紀錄prefix sum在哪個node
---
## 1669. Merge In Between Linked Lists
```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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
ListNode* root = list2;
ListNode* prev = NULL;
ListNode* list2_end = NULL;
while(root->next!=NULL)
root = root->next;
list2_end = root;
root = list1;
int count = 0;
while(root!=NULL){
if(count == a){
prev->next = list2;
}
if(count == b){
list2_end->next = root->next;
break;
}
prev = root;
root = root->next;
if(count>=a && count<=b)
delete prev;
count++;
}
return list1;
}
};
```
### Notes:
1. 紀錄prev node，當count==a時，prev->next = list2
2. 當count==b，list2_end->next = current->next
3. 核心概念如上。
---
## 234. Palindrome Linked List
```c=
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
ListNode* reverse(ListNode* head){
ListNode* temp = head;
ListNode* prev = NULL;
ListNode* next = NULL;
while(temp != NULL){
next = temp->next;
temp->next = prev;
prev = temp;
temp = next;
}
return prev;
}
bool isPalindrome(struct ListNode* head) {
if(head->next == NULL)
return true;
int count = 0;
ListNode* slow = head;
ListNode* fast = head;
ListNode* node1 = head;
ListNode* node2 = head;
ListNode* cut = NULL;
// find the middle node of List
while(head){
if(fast!=NULL && fast->next != NULL){
cut = slow;
slow = slow->next;
fast = fast->next->next;
}
count++;
head = head->next;
}
cut->next = NULL;
// reverse nodes which located after middle node.
if(count % 2 == 0){
node2 = reverse(slow);
}
else{
node2 = reverse(slow->next);
}
for(int i=0; i<(int)(count/2); i++){
if(node1->val != node2->val)
return false;
node1 = node1->next;
node2 = node2->next;
}
return true;
}
```
### Notes:
1. 這題如果不考慮follow-up的部分的話，就花O(n)的space把所有element紀錄下來，再for loop判斷是否回palindrome即可
2. follow-up: 其實只要找到middle node，並且把middle node後面的linked list給反轉，就可以不用花費O(N)的space來記錄了。
---
## 445. Add Two Numbers 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* reverse(ListNode* head){
ListNode* prev = NULL;
ListNode* next = NULL;
while(head!=NULL){
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
l1 = reverse(l1);
l2 = reverse(l2);
ListNode* newNode, *prev = NULL;
int carry = 0, temp=0;
while(l1!=NULL || l2!=NULL){
if(l1!=NULL && l2!=NULL){
temp = carry + l1->val + l2->val;
l1 = l1->next; l2 = l2->next;
}
else if(l1==NULL && l2!=NULL){
temp = l2->val + carry;
l2 = l2->next;
}
else if(l1!=NULL && l2==NULL){
temp = l1->val + carry;
l1 = l1->next;
}
newNode = new ListNode(temp%10);
carry = int(temp/10);
newNode->next = prev;
prev = newNode;
}
if(carry != 0){
newNode = new ListNode(carry);
newNode->next = prev;
prev = newNode;
}
return prev;
}
};
```
### Notes:
1. 沒考慮follow-up
2. 先把兩個linked-list做reverse
3. 再從頭開始累加，並同時做reverse
4. Time: O(N), Space: O(N)
Sign in with Wallet
Connect another wallet