# C: Linked List Problem Set

###### tags: `C_LANGUAGE`

* Reverse Linked List(Pre, cur, Tail)

/*
    Time Compilexity: O(N)
    
    Three Pointer: pre, cur, tail

    Every time makes the changes the current node's next to before one.
      
    Spacial Case One:
        (1)"First Time"
            e.g:pre->NULL
        (2)"Last Time"
            Return the last node and make the last's node's member(next) of linkeind list 
            point to the previous one.
*/
 //error handling
    if(head == NULL)
        return head;
    
    struct ListNode *pre = NULL;
    struct ListNode *cur = head;
    struct ListNode *tail = cur->next;
    
    while(cur->next){
        cur->next = pre;
        pre = cur;
        cur = tail;
        tail = tail->next;
    }
    cur->next = pre;
    return cur;

880. Remove Duplicates from Sorted List
* 小心if else 的選項

struct ListNode* deleteDuplicates(struct ListNode* head){
    
    if(NULL == head)
        return NULL;
    
    struct ListNode *cur = head;
    struct ListNode *tmp = cur;
    
    while(cur->next){
        tmp = cur->next;
        
        if(cur->val == tmp->val){
            cur->next = tmp->next;
        }else{
            cur = cur->next;
        }
    }
    return head;
}

881. Delete Node in a Linked List
882. Linked List Cycle

## Sorting:
21. Merge Two Sorted Lists

## Better Way to Remove the List Node?

* Remove List Node

void remove_list_node(List *list, Node *target) {
    Node *prev = NULL;
    Node *current = list->head;
    while (current != target) {
        prev = current;
        current = current->next;
    }
    if (!prev)
        list->head = target->next;
    else
        prev->next = target->next;
}

### Better Way? ptr to ptr? Feeling confused
[Jserv's Review](https://www.ptt.cc/bbs/Gossiping/M.1547666654.A.446.html)-

> That is a simple way... Just draw the linkedlist by your hand, don't be lazy
#### Could You explain for this? How could use ptr to ptr to do in the remove node case

void remove_list_node(List *list, Node *target) {
    Node **indirect = &list->head;
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

## Smart Way
### Add Entry
#### why we may use the ptr to ptr to replace value
也就是說我能夠用 indirect 追蹤 head 指到哪裡(對 indirect 取值便能得到 head 的位址，儘管 head 指向不同位址)
* pass by value
* pass by reference

void add_entry(node_t **head, int new_value)
{
    node_t **indirect = head;

    node_t *new_node = malloc(sizeof(node_t));
    new_node->value = new_value;
    new_node->next = NULL;

    assert(new_node);
    while (*indirect)
        indirect = &(*indirect)->next;
    
    *indirect = new_node;
}

> 注意當我們到最後一個node(指向NULL的那個node),我們想要利用indirect改變last node裡面next指標((*indirect)->next) 指向我們新create的node,因此我們需要將它assign到新得node必須先將indirect指標assign給indirect指標
* While Loop with Ptr to Ptr

indirect = &(*indirect)->next;

indirect = &((*indirect)->next)

也就是說我們在控制最後一個node的next指標, 也就是將這個last_node得next指標位置assign給 indirect(指向指標得指標)

## Remove Linked List

## Reference
[一行一行的解析](https://hackmd.io/@joey3639570/BJwdSCBVv)
[RinHizakura Linekd List](https://hackmd.io/@RinHizakura/SJUTL6E4w/%2FpnWNdj5HT4KFAgkikkWE6A)
[github_Reference_RinHizakura](https://github.com/RinHizakura/linked-list)
[Good Taste of Pointer](https://github.com/mkirchner/linked-list-good-taste)
[JSERV_linkedList_collection](https://hackmd.io/@sysprog/2020-homework1)
[Diagram_Explain](https://hackmd.io/@MingRuey/2020q3-quiz1)