info2023-homework2
===

🧔：interviewer 👶：interviewee

[206. Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/ "游標顯示")
---
>[video](https://youtu.be/wOW2LUXLedY)
>
影片: 28:35

測驗說明與問答

🧔：你好,我是全聯電子的工程師,很高興能請你來參加這次的coding面試,然後這邊有準備一道題目來做一個程式方面的交流,那我會給你一個linklist,他會由1->2->3,並希望你能reverse整條linklist讓他變成3->2->１又或者5->4->3->2->1變1->2->3->4->5，最後希望你用c語言來作答

👶：(作答中)

#include <stdio.h>
#include <stdlib.h>

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

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL){
        return NULL;
    }
    if(head -> next == NULL){
        return head;
    }
    
    struct ListNode *temp_prev = head;
    struct ListNode *temp_next = head;
    struct ListNode *temp_cur = head;

    temp_next = temp_next -> next;
    
    if(temp_next -> next != NULL){
        temp_next = temp_next -> next;
    }else{
        temp_next -> next = temp_cur;
        temp_cur -> next = NULL;
        head = temp_next;
        return head;
    }

    temp_cur = temp_cur -> next;
    temp_prev -> next = NULL;
    temp_cur -> next = temp_prev;
    temp_prev = temp_cur;
    temp_cur = temp_next;

    while(temp_next ->next != NULL){
        temp_next = temp_next -> next;
        temp_cur ->next = temp_prev;
        temp_prev = temp_cur;
        temp_cur = temp_next;
    }

    temp_cur -> next = temp_prev;
    head = temp_cur;
    return head;
}

🧔：那你可以分析一下你這樣做的時間複雜度嗎？

👶：我要走完整個list,所以時間會是O(n),而每個for-loop裡面的操作則是O(1),所以整體時間為O(n)

🧔：那像這樣你有沒有考慮用recursive的方式來寫呢

👶：如果用recursive的話我會用以下這樣的寫法(coding)

struct ListNode *reverseList(struct ListNode *head){
	return reverse(NULL, head);
}

struct ListNode *reverse(struct ListNode *pre, struct *cur){
    if(cur == NULL){
        return pre;
    }
    struct ListNode *temp = cur ->next;
    cur ->next = pre;
    return reverse(cur, temp);
}

🧔：那這邊你完成的不錯，但我現在希望你能把這樣的題目做一個延伸像是螢幕上這樣會給你一個linklist的head pointer以及left 跟right兩個值分別代表要reverse的左邊起始以及右邊結尾，像是我會給你head = 1,2,3,4,5 代表linklist 長這樣1->2->3->4->5，然後給你的left = 2,right = 4 就表示你要給我的結果會長得像1->4->3->2->5，那這樣有什麼問題嗎

👶：那有沒有可能left跟right的值會不在linklist裡面呢,還有有沒有可能left會等於right的值

🧔：left跟right的值一定都會在裡面,然後left跟right的值是有可能一樣的喔，那還有什麼問題想問的嗎

👶：那我沒有問題了(開始coding)

struct ListNode *reverseList(struct ListNode *head, int left, int right){

    if(head == NULL){
        return NULL;
    }
    if(head ->next == NULL){
	    return head;
    }
    
    struct Listnode *dummy = malloc(sizeof(struct ListNode));
    dummy -> next = head;

    struct ListNode *prev = dummy;


    for(int i = 0; i<left -1; i++){
        prev = prev->next;
    }
    struct ListNode *current = prev->next;

    for(int i = 0 ;i<right -left;i++){
        struct ListNode *next_node = current -> next;
        current->next = next_node ->next;
        next_node ->next = prev ->next;
        prev ->next = next_node;
    }
	
	struct ListNode *new_head = dummy_next;
	free(dummy);

	return newhead;
}

🧔：好那很感謝真蝦同學你來參加今天的面試,那我們有結果會再通知您

---
## 同儕指教

- 了解了自己對recursive的定義卻是有一點不太對,也就尤其指出做了一些修正
- 在面試過程以interviewee的角色應該要盡可能的延伸題目，以及將題目盡可能地融入公司的實際情形才對，但這方面尚有不足
- 影片沒聲音的部分竟然沒有注意到（會重新上傳）
- 鍵盤敲擊聲音過大，有盡量小力一點
- 互動的部分也有多加了一些，但還是稍嫌不足