---
# System prepended metadata

title: Linked List
tags: [EMBEDDED_C]

---

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