Neetcode 150 — LinkedList
9 min readOct 16, 2026
最近為了練習刷題，開始寫 Neetcode 150。以下是我的刷題筆記，主要以 JAVA 來練習，分類及題目來自 Neetcode。
1. Reverse Linked List
// 1.
// 把node移到前面去
// tail.next = next.next
// next.next = head
// head = next
// tail next
// ex. head = [0,1,2,3] -> [3,2,1,0]
//
// 假設有 n 個 node
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// [0,1,2,3] -> [3,2,1,0]
// [] -> []
// [1] -> [1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
ListNode result = head;
while (head.next != null) {
ListNode next = head.next;
head.next = next.next;
next.next = result;
result = next;
}
return result;
}
}2. Merge Two Sorted Linked Lists
// 1.
// 先有一個 dummyHead，接下來比較 list1 和 list2 的第一個數字，
// dummyHead.next會是比較小的那一個，接著再繼續往下比較，
// 直到其中一個list沒有值了，則直接接起另一個 list
// ex. list1 = [1,2,4], list2 = [1,3,5]
// dummyHead=[-1],cur=dummyHead,list1=1,list2=1,list1<=list2,
// cur.next=list1, list1=list1.next
// ...
// 假設 list1 有 n 個 node, list2 有 m 個 node
// Time complexity: O(n+m)
// Space complexity: O(1)
//
// Dry run
// list1 = [1,2,4], list2 = [1,3,5] -> [1,1,2,3,4,5]
// list1 = [1,2,3], list2 = [] -> [1,2,3]
//
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
if (list1 != null) {
cur.next = list1;
} else {
cur.next = list2;
}
return dummy.next;
}
}3. Linked List Cycle Detection
// 1. Floyd's Cycle Detection Algorithm（快慢指標）
// 如果有cycle，slow一次走一步，fast一次走兩步，兩個一定會在 cycle 內相遇
//
// 假設 list 有 n 個 node
// 假設沒有cycle，則fast走n/2步會到終點
// 假設有cycle，fast和slow每走一次，就會拉近距離一步，假設cycle有k步，則k步內一定會相遇
// 而且 k < n，所以 Time complexity: O(n)
// Space complexity: O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}4. Reorder Linked List
// 1. 每次都找最後一個
// ex. [0,1,2,3,4,5,6] -> [0,6,1,5,2,4,3]
// dummy=[-1], cur = dummy
// cur.next = front, front = front.next, cur = cur.next
// front走到最後一個的前面，cur.next = prev.next, prev.next=null, cur=cur.next
//
// 假設 list 有 n 個 node
// Time complexity: O(n-1 + n-3 + ...1)=O(n^2)
// Space complexity: O(1)
// 2. slow&fast and reverse linked list and merge
// 可以先利用 slow & fast 走到中間，然後把中間之後的list reverse
// 最後再 merge 兩個 list
// ex. [0,1,2,3,4,5,6]
// slow=fast=0;slow=1,fast=2;slow=2,fast=4;slow=3,fast=6 -> 走到中間
// second=slow.next;slow=null -> 讓前面的 list 和後面的 list 切斷
// while (second.next != null) {....} -> reverse
// first=[0,1,2,3], second=[4,5,6] -> merge
// ex. [0,1,2,3,4,5,6,7] -> slow=3,fast=6, 但切下來first=[0-3],seond=[4-7]是一樣數量的
//
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// [0,1,2,3,4,5,6] -> [0,6,1,5,2,4,3]
// [1] -> [1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode second = slow.reverse(slow.next);
slow.next = null;
ListNode first = head;
while (second != null) {
ListNode nextFirst = first.next;
ListNode nextSecond = second.next;
first.next = second;
second.next = nextFirst;
first = nextFirst;
second = nextSecond;
}
}
private ListNode reverse(ListNode node) {
if (node == null) {
return null;
}
ListNode head = node;
while (node.next != null) {
ListNode next = node.next;
node.next = next.next;
next.next = head;
head = next;
}
return head;
}
}5. Remove Nth Node From End of List
// 1. slow & fast
// 先用一個 dummyNode.next = head
// 可以利用 slow & fast，讓 fast 先走 n 步，
// 然後 slow 和 fast 一起一次走一步，直到 fast.next==null
// ex. head = [1,2,3,4], n = 2
// slow=dummy,fast=2;slow=1,fast=3;slow=2,fast=4
// slow.next=slow.next.next
// ex. head = [1,2,3,4], n=4
// slow=dummy,fast=4
// slow.next=slow.next.next
//
// 假設 list 有 n 個值
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// head = [1,2,3,4], n = 2
// head = [1,2,3,4], n = 4
// head = [1,2,3,4], n = 1
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}Get AShiou’s stories in your inbox
Join Medium for free to get updates from this writer.
6. Copy Linked List with Random Pointer
// 1. hashmap
// 可以先loop建新的linked list，然後把每個舊node當作hashmap的key，新node當作value
// 然後再for loop 一次舊的linked list，
// 把node和random Node，都在hashmap查，然後用新的 node 連線
// ex. head = [[3,null],[7,3],[4,0],[5,1]]
//
// 假設 list 有 n 個 node
// Time complexity: O(n)
// Space complexity: O(n)
//
// Dry run
// head = [[3,null],[7,3],[4,0],[5,1]]
// head = []
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
Map<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while (cur != null) {
Node tmp = map.get(cur);
tmp.next = map.get(cur.next);
tmp.random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}7. Add Two Numbers
// 1.
// 邊 for loop 邊把每個值相加，並new一個出來
// ex. l1 = [1,2,3], l2 = [4,5,6]
// 假設l1長度n, l2長度m
// Time complexity: O(max(m, n))
// Space complexity: O(max(m, n))
//
// Dry run
// l1 = [1,2,3], l2 = [4,5,6] -> [5, 7, 9]
// l1 = [1,2,4], l2 = [4,5,6] -> [5, 7, 0, 1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry == 1) {
int sum = carry;
if (l1 != null) {
sum = sum + l1.val;
}
if (l2 != null) {
sum = sum + l2.val;
}
cur.next = new ListNode(sum % 10);
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
cur = cur.next;
}
return dummy.next;
}
}8. Find the Duplicate Number
// 1. Hashset
// for loop 的過程，把數字放進 hashset，如果已經在 hashset 代表重複
// ex. nums = [1,2,3,2,2]
//
// 假設 nums 有 n 數字
// Time complexity: O(n)
// Space complexity: O(n)
// 2. Sort
// 題目有提到希望用 O(1) 的 space complexity，並且數字有n+1個，範圍在[1,n]，
// 有一個數字重複，但可能重複多次
// 可以先 sort，再看是否跟前面的值一樣
//
// 假設 nums 有 n 數字
// Time complexity: O(nlogn)
// Space complexity: O(1)
// 3. Floyd's Cycle Detection
// 但題目又有提到，不可以修改 nums array，因此也不能 sort
// 可以透過 slow, fast 兩個快慢 pointer 前進，把nums內的數值當作下一個index，
// 如果有重複的數值，代表會形成一個 cycle，而 cycle的環入口就是重複點。
//
// 假設起點到環入口長度為a，環入口到slow,fast相遇點為b,相遇點到環入口為c
// ---b---
// / \
// 起點---a---環入口 相遇點
// \ /
// ---c---
// slow走a+b,fast走2(a+b)
// 2(a+b)=(a+b)+k(b+c) //假設相遇前，fast已經繞了k圈
// 2a+2b=a+b+kb+kc
// a = (k-1)b + kc
// a = (k-1)(b+c)+c -> 代表接下兩個pointer分別從起點和相遇點開始走，相遇時就是環入口
//
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// [1,2,3,2,2] -> 2
// [1,2,4,4] -> 4
class Solution {
public int findDuplicate(int[] nums) {
// 找到第一個相遇點
int slow = nums[0];
int fast = nums[nums[0]];
while (slow != fast) {
slow = nums[slow];
fast = nums[nums[fast]];
}
// slow 回到起點
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}9. LRU Cache
// 1. Brute Force
// 可以用hashmap紀錄key和value，
// 然後再一個hashmap用來記錄key及value為最近使用的timestamp，
// 要刪除時，則把 timestamp 最小的那一個刪除
//
// 假設 capacity 是 n
// Time complexity: get:O(1),put:O(1),要刪除時:O(n)
// Space complexity: O(n)
// 2. hashmap + doubly linkedlist
// 將 value 包成一個 node，然後用 hashmap 紀錄 key 和 node
// 差別在多用了 doubly linkedlist 在每次使用時，把值刪除，然後移到 head
//
// Time complexity: get:O(1), put:O(1)
// Space complexity: O(n)
class LRUCache {
private Map<Integer, Node> map;
private int capacity;
private Node head;
private Node tail;
class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.prev = this.head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node tmp = map.get(key);
remove(tmp);
addToHead(tmp);
return tmp.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
remove(map.get(key));
}
Node waitAdd = new Node(key, value);
map.put(key, waitAdd);
addToHead(waitAdd);
if (map.size() > capacity) {
Node waitRemove = tail.prev;
remove(waitRemove);
map.remove(waitRemove.key);
}
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}10. Merge K Sorted Linked Lists
// 1. merge two linked list
// 把第一個和第二個 list merge, 接下來再和第三個 merge, ...
// ex. lists = [[1,2,4],[1,3,5],[3,6]]
// 假設每個 list 有 n 個值
// Time complexity: O(n+2n+...kn)=O(nk^2)
// Space complexity: O(1)
// 2. minHeap
// 把每一個list的第一個數字放進minHeap，
// 接著每次從minHeap拿出值並且把該list.next放進minHeap，直到minHeap沒有值。
// Time complexity: O(nklogk)
// Space complexity: O(k)
//
// Dry run
// [[1,2,4],[1,3,5],[3,6]] -> [1,1,2,3,3,5,6]
// [[]] -> []
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
for (ListNode node : lists) {
if (node != null) {
minHeap.offer(node);
}
}
while (!minHeap.isEmpty()) {
ListNode tmp = minHeap.poll();
if (tmp.next != null) {
minHeap.offer(tmp.next);
}
cur.next = tmp;
cur = tmp;
}
return dummy.next;
}
}11. Reverse Nodes in K-Group
// 1.
// 每 k 個 node 要進行翻轉一次，所以我可以一個node cur指向head
// next = cur.next;
// cur.next = next.next;
// next.next = cur;
// head = next;
// cur 接下一個循環的結果;
// 同時需要一個tail來接每一次的結果。
//
// ex. head = [1,2,3,4,5,6], k = 3
//
// Time complexity: O(n)
// Space complexity: O(1)
//
// Dry run
// head = [1,2,3,4,5,6], k = 3 -> [3,2,1,6,5,4]
// head = [1,2,3,4,5,6,7], k = 3 -> [3,2,1,6,5,4,7]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode tail = dummy;
ListNode cur = head;
while (cur != null) {
ListNode tmp = getKth(cur, k);
if (tmp == null) {
break;
}
for (int i = 1; i < k; i++) {
ListNode next = cur.next;
cur.next = next.next;
next.next = tail.next;
tail.next = next;
}
tail = cur;
cur = cur.next;
}
return dummy.next;
}
private ListNode getKth(ListNode node, int k) {
for (int i = 1; i < k; i++) {
node = node.next;
if (node == null) {
return null;
}
}
return node;
}
}
