鏈表

A collection of 6 posts
[Leetcode] 160. Intersection of two Linked Lists (相交鏈表) 題解紀錄
鏈表

[Leetcode] 160. Intersection of two Linked Lists (相交鏈表) 題解紀錄

題目: Intersection of two Linked Lists (相交鏈表) 難度: 簡單 解題思路: 這一題如果要做到空間複雜度為 O(1) 的話，需要使用到雙指針的方式來解題，主要原理就如同上圖 可以把兩條鏈表相交匯的部分，分離成第三個鏈表來看: 鏈表a 的 指針 定義為 (p_a) 鏈表b 的 指針 定義為 (p_b) 分開看的 鏈表c 定義為 (C) 這樣我們就可以得出 (p_a + p_b) == (p_b + p_a)， 那如果 p_a -> C -> p_
2 min read
[Leetcode] 19. Remove nth node from end of list (删除鏈表的倒數第 N 個節點) 題解紀錄
鏈表

[Leetcode] 19. Remove nth node from end of list (删除鏈表的倒數第 N 個節點) 題解紀錄

題目: Remove nth node from end of list (删除鏈表的倒數第 N 個節點) 難度: 中等 題解思路: 這一題主要是需要使用雙指針來實現 假設 n 是 總長度 假設 k 是 步數 1. 雙指針思路 如果快指針先走 k 步，再讓慢指針和快指針一起走到快指針的底部，這樣子的話，慢指針走到的節點就會是 n-k+1 的節點了，所以這樣子會有兩次迴圈，第一次是走到 k ，第二次是把剩下的長度走完 2. 虛擬頭節點 如上面所說，因為慢指針會走到的節點會是 n-k+1 ，而題目要求我們返回的是 n-k，所以我們需要使用虛擬頭節點來解決，把 n-k+1
1 min read
[Leetcode] 83. Remove Duplicates from Sorted List (删除排序链表中的重复元素) 題解紀錄
鏈表

[Leetcode] 83. Remove Duplicates from Sorted List (删除排序链表中的重复元素) 題解紀錄

題目: Remove duplicates from sorted list (删除排序链表中的重复元素) 難度: 簡單 題解思路: 這一題我第一次主要是使用雙指針來解決的，但這一題其實可以使用更好的方式來解決，大意了沒有閃，但我還是來講解一下我這一題的主要思路 1. 設置邊界條件 主要是需要處理鏈表節點為 1 的情況，直接返回 head 2. 快慢指針比對後刪除節點 把快指針的下一個指向慢指針的下一個，就相當於刪除了快指針的節點，只不過這時候要注意的是，快指針還指向那個被刪除的節點，所以需要把快指針指向快指針的下一個節點，這樣子就完成刪除節點的操作，至於那個被刪掉的節點 ? 因為python有垃圾回收機制，所以我就隨他去啦
1 min read
[Leetcode] 86. Partition List (分隔鏈表) 題解紀錄
鏈表

[Leetcode] 86. Partition List (分隔鏈表) 題解紀錄

題目: Partition list (分隔鏈表) 難度: 中等 題目要求: 題目給定一組鏈表和一個目標值(x)，需要返回一組鏈表，鏈表中小於 x 的節點都會出現在大的節點之前，並且保留鏈表中節點的初始相對位置 解題思路: 這題主要的解法是用兩個鏈表作為儲存，一個鏈表儲存小於 x 節點，一個鏈表儲存大於 x 的節點，最終再把兩個鏈表作合併就會是答案了 下面有幾的地方需要注意 1. 儲存的鏈表需要設置虛擬頭節點 因為需要照順序來排序鏈表，所以需要創建虛擬頭節點來指向每個節點的( next ) 2. 需要宣告指針來操作儲存的鏈表 主要是因為最後一段在拚湊和返回鏈表的時候，需要使用到頭部節點和尾部節點，使用指針的話，就可以在迴圈完成後同時訪問鏈表的頭部節點和尾部節點，做拼湊和返回的操作 這題的時間複雜度為 O(n)，空間複雜度也為 O(n)
1 min read
[Leetcode] 876. Middle of the Linked List (鏈表的中間節點) 題解紀錄
鏈表

[Leetcode] 876. Middle of the Linked List (鏈表的中間節點) 題解紀錄

題目: Middle of the linked list (鏈表的中間節點) 難度: 簡單 題目要求: 題目給定一個非空的單鏈表，返回鏈表的中間節點。 如果鏈表有兩個中間節點，則返回第二個中間節點。 解題思路: 因為題目給定的是單向鏈表(Linded List)，所以我們只能透過迴圈的方式一個一個取得鏈表所有節點的資料。 那這題要怎麼解決呢? 可以透過雙指針的方式來解決。 想像一下，當兩個人開始同時走一條路，而第一個人的速度正好是第二個人速度的兩倍，所以當第一個人走到終點的時候，第二個人剛好會走到路途的正中間。 依照上面的思路，我們可以知道當快指針的速度是慢指針兩倍的時，快指針走到尾部，慢指針也剛好會到鏈表的正中間。
1 min read
[Leetcode] 234. Palindrome Linked List (回文鏈表) 題解紀錄
鏈表

[Leetcode] 234. Palindrome Linked List (回文鏈表) 題解紀錄

leetcode 234 題解紀錄 前言: 最近開始上手刷leetcode，這幾天主要是在刷鏈表的演算法，想透過博客來記錄自己的成長歷程，也順便記錄一下自己解題時候的思路 題目要求: 這一題叫做回文鏈表，剛開始看題目的時候，會有點難理解題意，但其實這題的概念很簡單，就是把鏈表從中間拆成兩半，並且後半段的資料反過來時，資料會跟前半段的資料相同，這樣就是一個合格的回文鏈表。 解題思路: 這題的解法主要是利用雙指針先找到鏈表的中間點， 思路是先創建快慢指針，而快指針速度剛好是慢指針速度的兩倍，這樣子快指針跑到鏈表尾部的時候，慢指針剛好會停在鏈表的中間點，這樣我們就可以得到鏈表後半段的資料 但因為這時候後半段的資料是反的，所以我們需要把後半段的資料倒轉過來，以便跟前半段的資料比對，把後半段的資料倒轉過來以後，就可以跟前半段的資料照順序比對了
2 min read