# Linked List ###### tags: `EMBEDDED_C` * [Linked List](https://hackmd.io/79VYwlLGTy6jWcsUicMBpw?view) #### a. 基本:print, push, add, pop, delete, search、recursive #### b. 應用:reverse, sort, merge, split 多個list, 找出是否有環, Sorting in Linked List(Bubble Sort),Time and Space Complexity #### c. merge sort linked list, linked list Sorting，我是使用Seletion Sort解決這題(因為覺得Merge和Quick sort好難用linked list寫) ## Linked List Problemn Bucket List - [ ] Implement the Stack with Linked List - [ ] Implement the Queue with Linked List - [ ] 21. Merge Two Sorted Lists - [ ] 234. Palindrome Linked List - [x] 206. Reverse Linked List - [ ] 160. Intersection of Two Linked Lists - [x] 141. Linked List Cycle - [x] 876. Middle of the Linked List - [x] 1290. Convert Binary Number in a Linked List to I - [ ] 237. Delete Node in a Linked List - [ ] 83. Remove Duplicates from Sorted List - [ ] 203. Remove Linked List Elements - [ ] 83. Remove Duplicates from Sorted List [Reference](https://hackmd.io/79VYwlLGTy6jWcsUicMBpw?view) ### 206. Reverse Linked List ```clike= struct ListNode* reverseList(struct ListNode* head){ if(head == NULL) return NULL; struct ListNode *pre = NULL; struct ListNode *cur = head; struct ListNode *tail = head->next; while(cur && cur->next) { cur->next = pre; pre = cur; cur = tail; tail = tail->next; } cur->next = pre; return cur; } ``` ### 21. Merge Two Sorted Lists ### 234. Palindrome Linked List ### 206. Reverse Linked List ### 160. Intersection of Two Linked Lists ### 141. Linked List Cycle ### 876. Middle of the Linked List ### 1290. Convert Binary Number in a Linked List to I ### 237. Delete Node in a Linked List ```cpp= void deleteNode(struct ListNode* node) { struct ListNode *tmp = node->next; node->val = tmp->val; node->next = tmp->next; free(tmp); } ``` ### 83. Remove Duplicates from Sorted List * cornor case 沒過.....再想一下 ```cpp= struct ListNode* deleteDuplicates(struct ListNode* head){ if(NULL == head) return NULL; struct ListNode *cur = head; while( cur && cur->next){ if (cur->val == cur->next->val){ struct ListNode *tmp = cur->next; cur->next = cur->next->next; free(tmp); } else cur = cur->next; } return head; } ``` ### 203. Remove Linked List Elements ```cpp= struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode *curr_node = head; struct ListNode *tmp = head; if (head == NULL){ return head; } while(curr_node->next != NULL){ if (val == curr_node->next->val){ tmp = curr_node->next; curr_node->next = curr_node->next->next; free(tmp); } else{ curr_node = curr_node->next; } } //special case if (head->val==val) { head=head->next; } return head; } ``` ### 第二題考排序linked list 我是使用Seletion Sort解決這題(因為覺得Merge和Quick sort好難用linked list寫) ```cpp= struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode** nextPtr = &head; while (*nextPtr) { if ((*nextPtr)->val == val) { *nextPtr = (*nextPtr)->next; } else { nextPtr = &((*nextPtr)->next); } } return head; } //I don't think these would work ``` ## Reference Interview * [3 round reference](https://hackmd.io/9dG1xXtETvG2a1KB-7RIcw?view) * [Phone Interview](https://hackmd.io/nvIlIRclRvq4-xEmpWCZjA?view) * [PTT Oversea](https://www.ptt.cc/bbs/Oversea_Job/M.1597533013.A.523.html) * [Scalable in C](https://hintjens.gitbooks.io/scalable-c/content/preface.html) * [Function_Ptr State Machine](https://github.com/gbmhunter/FunctionPointerStateMachineExample) * [底層C語言的世界](https://ccckmit.gitbooks.io/lowlevelc/content/header.html) * [Common concept of C/C++ fromkshuang's Wiki](https://www.kshuang.xyz/doku.php/programming:c:common_concept_of_c) * [軟韌體工程師面試常考之考古](https://www.ptt.cc/bbs/NTUE-CS100/M.1300374249.A.C8F.html) * [PTT Reference1](https://www.ptt.cc/bbs/Tech_Job/M.1625414794.A.C93.html) * [PTT Reference 2](https://www.ptt.cc/man/Tech_Job/DB04/D730/DE21/M.1524923943.A.F17.html)