【算法筆記】連結清單相關

LC141 環形連結清單

注意快慢指針的使用

bool hasCycle(ListNode *head) {
    //快慢指針
    if(head == nullptr) return false;
    ListNode *fast = head, *slow = head;
    while(fast->next && fast->next->next) {
        /*
        * 在連結清單中隻有一個節點時，快慢指針都為nullptr，傳回true，錯誤！
        * fast = fast->next ? fast->next->next : fast->next;
        */
        slow = slow->next;
        fast = fast->nex
        if(fast == slow) return true; //指針相遇，則有環
    }
    return false;
}
           

LC206 反轉連結清單

//疊代
ListNode* reverseList(ListNode* head) {
    ListNode *cur = head, *pre = nullptr;
    while(cur) {
        ListNode *tmp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

//遞歸
ListNode* reverseList(ListNode* head) {
    return reverse(head, nullptr);
}
ListNode* reverse(ListNode* cur, ListNode* pre) {
    if(cur == nullptr) return pre;
    ListNode *tmp = cur->next;
    cur->next = pre;
    return reverse(tmp, cur);
}
           

LC234 回文連結清單

時間複雜度：O(n)

空間複雜度：O(1)

bool isPalindrome(ListNode* head) {
    ListNode *slow = head, *fast = head, *prev = nullptr;
    //通過快慢指針找到連結清單中間位置
    while(fast) {
        slow = slow->next;
        /*
		* 注意slow最終的指向
		* 1->2->2->1
		*       |
		*     slow
		*/
        fast = fast->next ? fast->next->next : fast->next;
    }
    //反轉連結清單
    while(slow) {
        ListNode *tmp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = tmp;
    }
    //周遊檢查
    while(head && prev) {
        if(head->val != prev->val) return false;
        head = head->next;
        prev = prev->next;
    }
    return true;
}