# HW1
名稱：伏爾泰 Voltaire

## REACTO
Repeat：重複提問，確認自己理解題目要求
Examples： 針對題目條件，舉出合適的案例，不限於特例
Approach： 說明自己要採用的方法
Code： 撰寫程式
Test： 測試，若不能實際測試，就說明驗證程式的方案

## Merge two sorted lists
* There are two sorted lists, please merge them.

now we need to merge two sorted lists.
the data type for list node is int?
is singly linked list?
the range for data?
is sorted lists is in descending or ascending?
sorted in descending or ascending?
the range for node number in every list?

For example, with one list is 1, 2 , 5, 8. another is 1, 3, 4.
we want the result is 1, 1, 2, 3, 4, 5, 8

to implement it, avoid allocated additional memory. We can using pointer to pointer.
because while merge two sorted lists, what we really doing is to change every pointer of the node, making them to point to next desired node.
so we traverse list1, comparing every of its nodes to list2 nodes.

struct node {
    int val;
    struct node *next;
}

struct node *merge_two_sorted_lists(struct node *l1, struct node *l2)
{
    struct node *head = NULL;
    struct node **curr = &head;  
    while (l1 && l2) {
        if (l1->val < l2->val) {
            *curr = l1;
            l1 = l1->next;
        }
        else {
            *curr = l2;
            l2 = l2->next;
        }
        curr = &(*curr->next);
    }
    *curr = (uintptr_t) l1 | (uintptr_t) l2;
}

struct node {
    int val;
    struct node *next;
}

struct node *merge_two_sorted_list(struct node *l1, struct node *l2)
{
    struct node *head = NULL;
    struct node **curr = &head;
    
    while (l1 && l2) {
        if(l1->val < l2->val){
            
        }
        
    }
}

00:01 er：介紹題目
00:21 er：it is singly linked list
00:29 er：it is int
00:37 er：ascending order
02:37 er: sound resonable

## 231. Power of Two
請撰寫一個函式，判斷輸入的參數是否為 2 的冪次，回傳 true or false

1. 是什麼型別的參數, 是幾 bit

bool isPowerOfTwo(int n)
{
    if (n > 0 && (n & (n - 1)) == 0) return true;
    return false;
}

follow up：如果要順便計算是 2 的幾次方呢?
維持回傳 boolean

// one bit 1
bool isPowerOfTwo(int n)
{
	if (n <= 0) return false;

	int a, b;
	unsigned m = n & 0x7FFFFFFF;
	unsigned shift = 16, fb = 0;
	while (shift != 0){
		a = m >> shift;
		if (a) {
			m = a;
			fb += shift;
		}
		shift >>= 1;
	}
	if (n - (0x1 << fb) != 0) return false;
	return true;
}

最差情況，32 bit 整數比對 5 次，64 bit 比對 8 次。

## 19. Remove Nth Node From End of List
請你實作鏈結串列刪除尾端數來第 n 個節點的操作
singly linked list, 數值是 int

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if (!head || n <= 0) return head;
    struct ListNode **fast = &head, **slow = &head;

    for (int i = 0; i < n; i++){
        if (*fast == NULL) return head;
        fast = &((*fast)->next);
    }

    while (*fast != NULL) {
        fast = &((*fast)->next);
        slow = &((*slow)->next);
    }
    struct ListNode *node = *slow;
    *slow = (*slow)->next;
    free(node);

    return head;
}

follow-up：如果是給的是環狀鏈結串列呢? 會有甚麼影響?