Leetcode - 141. Linked List Cycle

-

想法:

硬記解法

利用快慢指針的概念

快的一次移動兩個位置

慢的一次移動一個位置

照理來說快的跟慢的不會碰到

如果快慢指針有碰到就表示該 list 有循環

如果快的碰到終點就表示該 list 沒有循環

code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Node;

bool hasCycle(Node *head) {
    Node* slow = head;
    Node* fast = head;

    if(head == NULL){
        return 0;
    }

    while(fast->next != NULL){
        fast = fast->next->next;
        if(!fast){
            return 0;
        }
        slow = slow->next;
        if(fast == slow){
            return 1;
        }
    }

    return 0;
}

ref:

刷題筆記｜Leetcode — Linked List Cycle 題組

留言

張貼留言

這個網誌中的熱門文章

Formal Verification(正規驗證)介紹和如何使用 SVA(System Verilog Assertion) 做驗證

-
圖片
(零)前提: 關於 Formal Verification，其實我也還不是很理解，而且資源也不是那麼多，尤其很多都只是觀念性的介紹，甚至寫得很艱澀難懂落落長，但沒實質提到該怎麼做 Formal Verification。 但據說驗證在 IC 設計上又是非常重要的，所以雖然這部分真的不好理解，還是硬著頭皮收集資料寫下這一篇，所以這篇也不會寫到太深，畢竟這整個要講起來是很專業領域的。 因此這篇適用於對 Formal Verification 完全不理解的人，希望可以幫助你入門。 (一)正文: 當我們完成一塊電路時，要怎麼確定功能跟預期的結果是一樣的？ 1. 在軟體內跑 Waveform，比對預期結果和實際結果     (1) 有 GUI，淺顯易懂     (2) 新手友善 2. 寫 Testbench，比對預期結果和實際結果     (1) 許多參數要自己設定     (2) 需要下點功夫才能理解 上述方法都是把所有的 Case 會產生的結果用手寫出來，然後再用人眼去比對每個預期結果和實際結果是不是一樣。 但此時問題來了，但如果今天有上千個 Case，還是只能靠我們自己把這上千個 Case 列出來，然後一一用人眼比對嗎？ 此時 Formal Verification 的功用就出來了！ 簡單來說它就是把你 電路該有的行為列成正規化的公式 然後再用一個 檢查器去確認你的電路的行為總是會跟這個公式所描述的行為 是一樣的 這部分對於一個新手來說可能真的會很 Hardcore 不過會了之後真的會變得很方便！ Functional Verification 把所有 Testcase 列出來然後作驗證。 Formal Verification (二)實驗: 安裝: 首先要安裝好這些東西 yosys symbiyosys gtkwave yices sudo apt-get install autoconfig lubgmp3-dev (Ubuntu) sudo yum install autoconfig lubgmp3-dev (CentOS，不過沒實際試過，只是猜測應該是這樣) 以上東西要怎麼裝，Google 就可以查到了 我本身的環境是使用 CentOS7，在安裝過程中也碰到蠻多坑的 (雖然後來還是自...
閱讀完整內容

Quartus Qsys + Nios II 入門使用

-
環境設置 OS: Windows 10 Software: Intel Quartus Prime Lite 18.0 Platform: Cyclone V GT 5CGTFD9E5F35C7 ================================================= Nios II 簡介 Nios II 為 Altera 所設計的 32-bit RISC soft-core CPU 其完全在 Altera 的 FPGA 板子上實現 版本有分為 f/s/e e是最便宜最簡單的 也是下面的實驗我們會選擇的版本 ================================================= Platform Designer 簡介 簡單來說 他就是可以用 Intel 的 IP 定義你的系統的工具 IP 之間的連接 或是對應到的位址之類的 所以如果要設計一個只有由 Intel IP 所組成的系統 這是非常方便的工具 ================================================= 以下實驗基本上都是參照 helloworld：基於Qsys的第一個Nios II系統設計 來去完成 所以有些詳細的步驟不在贅述 請直接參考網站裡面寫的 下面只會大概提到該做什麼事情 以及遇到的問題和解決方式 ================================================= 實驗 - Platform Designer 這裡主要是要建立 硬體 系統 步驟 1. 在 Quartus 建立新的專案 2. 建立 bdf 檔案 3. 點  Tool > Platform Designer，進到  Platform Designer 頁面 在這裡主要要新增 4 個元件 Nios II (classic) Processor On-Chip Memory (RAM or ROM) Intel FPGA IP JTAG UART Intel FPGA IP System ID Peripheral Intel FPGA IP 然後將該連的線連起來 每個元件的 clk 都要接到時鐘的 clk_out 每個元件的 reset 都要接到時鐘的 reset Nios II (clas...
閱讀完整內容

Quartus Qsys + Nios II + SDRAM 進階使用

-
圖片
環境設置 OS: Windows 10 Software: Intel Quartus Prime Lite 18.0 Platform: Cyclone V GT 5CGTFD9E5F35C7 基本上跟  Quartus Qsys + Nios II 入門使用  的步驟一樣 只有 Platform Designer 部分需要更改 ============================================== 新增 DDR3 SDRAM Controller with UniPhy IP ============================================== PHY Setting 頁面設定 Speed Grade: 7 (配合板子) Memory clock frequency: 400 MHz PLL reference clock frequency: 100 MHz Memory Preset: MT41J64M16LA-15E ============================================== Memory Parameter 頁面設定 Total Interface Width: 8 Memory Initialization Option > Memory CAS latency setting: 8 Output drive strength setting: RZQ/4 ODT Rtt nominal value: RZQ/4 Memory Write CAS latency setting: 6 Dynamic ODT(RTT/WR) value: RZQ/4 ============================================== Memory Timing 和 Board Setting 保持不動  ============================================== Controller Setting 頁面設定 打勾 Generate power-of-2 data bus widths for Qsys or SOPC Builder Maximum Avalon-MM burst lenght: ...
閱讀完整內容