1.環形鏈表

1.答案

package com.sunxiansheng.arithmetic.day11;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 141. 環形鏈表** @Author sun* @Create 2025/1/16 10:36* @Version 1.0*/
public class t141 {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;}
}

2.思路

快慢指針，只要相遇，就有環

2.兩數相加

1.答案

package com.sunxiansheng.arithmetic.day11;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 2. 兩數相加** @Author sun* @Create 2025/1/16 10:39* @Version 1.0*/
public class t2 {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 結果的頭節點ListNode res = new ListNode(-1);ListNode cur = res;// 進位int carry = 0;// 遍歷兩個鏈表的指針ListNode t1 = l1, t2 = l2;// 只要兩個鏈表有一個不為空就進行遍歷while (t1 != null || t2 != null) {// 獲取兩個節點的值int var1 = t1 == null ? 0 : t1.val;int var2 = t2 == null ? 0 : t2.val;// 求和int sum = var1 + var2 + carry;// 用完進位之后要恢復0carry = 0;// 判斷是否要進位if (sum > 9) {carry = sum / 10;sum = sum % 10;}// 給結果賦值cur.next = new ListNode(sum);cur = cur.next;// 移動指針if (t1 != null) {t1 = t1.next;}if (t2 != null) {t2 = t2.next;}}// 檢查是否還有沒處理的進位if (carry > 0) {cur.next = new ListNode(carry);}return res.next;}
}

2.結果

核心是有一個進位的字段，多注意即可

3.反轉鏈表

1.答案

package com.sunxiansheng.arithmetic.day12;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 206. 反轉鏈表** @Author sun* @Create 2025/1/17 09:56* @Version 1.0*/
public class t206 {public ListNode reverseList(ListNode head) {if (head == null) {return null;}// 哨兵節點ListNode dummy = new ListNode(0);dummy.next = head;// prevListNode prev = dummy;// startListNode start = head;// thenListNode then = start.next;while (start.next != null) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}return dummy.next;}
}

2.思路

首先需要有prev、start、then，然后只要start.next不為空，就進行反轉

4.反轉鏈表 II

1.答案

package com.sunxiansheng.arithmetic.day12;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 92. 反轉鏈表 II** @Author sun* @Create 2025/1/17 09:52* @Version 1.0*/
public class t92 {public ListNode reverseBetween(ListNode head, int left, int right) {// 找到prev、start、then// 哨兵節點ListNode dummy = new ListNode(0);dummy.next = head;// 讓cur指向left的前一個節點作為prevListNode cur = dummy;for (int i = 0; i < left - 1; i++) {cur = cur.next;}ListNode prev = cur;ListNode start = cur.next;ListNode then = start.next;// 遍歷次數int count = right - left;for (int i = 0; i < count; i++) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}return dummy.next;}
}

2.思路

找到prev、start、then，然后遍歷次數為right - left

5.K 個一組翻轉鏈表

1.答案

package com.sunxiansheng.arithmetic.day12;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 25. K 個一組翻轉鏈表** @Author sun* @Create 2025/1/17 10:21* @Version 1.0*/
public class t25 {public ListNode reverseKGroup(ListNode head, int k) {// 哨兵節點ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;// 提前記錄prevListNode prev = dummy;// 循環翻轉while (true) {// 先判斷有沒有一組for (int i = 0; i < k; i++) {cur = cur.next;// 只要發現沒有一組了，就返回結果if (cur == null) {return dummy.next;}}// 到這里就說明有一組，可以翻轉鏈表ListNode start = prev.next;ListNode then = start.next;reverseGroup(prev, start, then, k);// 更新prevprev = start;// 更新curcur = prev;}}/*** 翻轉一組鏈表** @param prev* @param start* @param then* @param k*/private void reverseGroup(ListNode prev, ListNode start, ListNode then, int k) {// 翻轉次數int count = k - 1;for (int i = 0; i < count; i++) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}}
}

2.思路

就是先判斷剩下的元素夠不夠k個，如果夠就進行反轉，翻轉之后要更新prev和cur

6.刪除鏈表的倒數第 N 個結點

1.答案

package com.sunxiansheng.arithmetic.day12;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 19. 刪除鏈表的倒數第 N 個結點** @Author sun* @Create 2025/1/17 10:44* @Version 1.0*/
public class t19 {public ListNode removeNthFromEnd(ListNode head, int n) {// 哨兵節點ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;// 求出一共有多少個節點int count = 0;while (cur.next != null) {cur = cur.next;count++;}// 倒數第n個節點的前一個節點的索引int index = count - n;cur = dummy;while (index > 0) {cur = cur.next;index--;}// 目前cur指向了前一個節點，可以開始刪除節點了cur.next = cur.next.next;return dummy.next;}
}

2.思路

就是先找到一共有多少個節點，再找到倒數第n個節點的前一個節點然后刪除

7.刪除排序鏈表中的重復元素 II

1.答案

package com.sunxiansheng.arithmetic.day13;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 82. 刪除排序鏈表中的重復元素 II** @Author sun* @Create 2025/1/19 09:32* @Version 1.0*/
public class t82 {public static ListNode deleteDuplicates(ListNode head) {// 哨兵節點ListNode dummy = new ListNode(300);dummy.next = head;ListNode cur = dummy;// 記錄前一個位置ListNode pre = dummy;while (cur.next != null) {cur = cur.next;if (cur.next == null || cur.val != cur.next.val) {pre = cur;} else {// 到這就說明pre的后兩個元素相同// 記錄一下值int val = cur.val;while (cur.next != null && val == cur.next.val) {cur = cur.next;}pre.next = cur.next;cur = pre;}}return dummy.next;}public static void main(String[] args) {ListNode head = new ListNode(1);head.next = new ListNode(1);head.next.next = new ListNode(1);head.next.next.next = new ListNode(2);head.next.next.next.next = new ListNode(3);deleteDuplicates(head);}
}

2.思路

就是有一個pre來記錄前一個位置，每次循環都讓cur先走一步，然后判斷當前元素跟下一個元素是不是相同，如果不相同或者目前是最后一個元素，就讓pre也指向cur，如果說當前元素跟下一個元素是相同的，那么就刪除相同元素，最終讓cur指向pre

8.旋轉鏈表

1.答案

package com.sunxiansheng.arithmetic.day13;import com.sunxiansheng.arithmetic.util.ListNode;import java.util.List;/*** Description: 61. 旋轉鏈表** @Author sun* @Create 2025/1/19 10:29* @Version 1.0*/
public class t61 {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null) {return head;}// 哨兵節點ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;// 計算鏈表總長度int length = 0;while (cur.next != null) {cur = cur.next;length++;}// 如果余數為0，則直接返回if (k % length == 0) {return head;}// 記錄鏈表末尾元素ListNode end = cur;// 移動到正數第length - k % length個位置int index = length - k % length;cur = dummy;while (index > 0) {cur = cur.next;index--;}dummy.next = cur.next;// 切斷，否則會有環cur.next = null;end.next = head;return dummy.next;}
}

2.思路

首先計算鏈表的總長度，然后記錄鏈表末尾元素，再通過計算，找到正數第length - k % length個位置，然后根據題意進行組裝，不過要注意切斷一下，否則會有環

9.LRU 緩存

1.答案

package com.sunxiansheng.arithmetic.day13;import java.util.HashMap;
import java.util.Map;/*** Description: 146. LRU 緩存** @Author sun* @Create 2025/1/19 10:55* @Version 1.0*/
public class LRUCache {// 雙向鏈表的節點class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int key, int value) {this.key = key;this.value = value;}}// 雙向鏈表的頭尾指針DLinkedNode head, tail;// map：key是key，value是雙向鏈表的節點private Map<Integer, DLinkedNode> map;// 容量private int capacity;public LRUCache(int capacity) {map = new HashMap<>();this.capacity = capacity;// 頭結點和尾節點head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}// 獲取元素public int get(int key) {// 從map中去獲取keyDLinkedNode dLinkedNode = map.get(key);if (dLinkedNode == null) {return -1;}// 獲取之后，將元素放到鏈表頭部moveToHead(dLinkedNode);return dLinkedNode.value;}private void moveToHead(DLinkedNode dLinkedNode) {// 首先需要在鏈表中刪除這個元素delete(dLinkedNode);// 然后將元素插入到頭部insertToHead(dLinkedNode);}private void insertToHead(DLinkedNode dLinkedNode) {dLinkedNode.next = head.next;dLinkedNode.prev = head;head.next.prev = dLinkedNode;head.next = dLinkedNode;}private static void delete(DLinkedNode dLinkedNode) {dLinkedNode.prev.next = dLinkedNode.next;dLinkedNode.next.prev = dLinkedNode.prev;}// 插入或更新元素public void put(int key, int value) {// 先獲取元素DLinkedNode dLinkedNode = map.get(key);// 如果元素有值了，就替換值，并移動到頭部if (dLinkedNode != null) {dLinkedNode.value = value;moveToHead(dLinkedNode);} else {// 沒有值則需要新增元素dLinkedNode = new DLinkedNode(key, value);// 確保容量足夠ensureCapacity(map.size() + 1);// 目前容量一定足夠，直接插入到頭部即可map.put(key, dLinkedNode);insertToHead(dLinkedNode);}}private void ensureCapacity(int newSize) {if (newSize <= capacity) {return;}// 如果容量不夠，則需要刪除最后的一個元素map.remove(tail.prev.key);delete(tail.prev);}
}

2.思路

使用雙向鏈表+map來做

首先需要一個雙向鏈表的類，key，value，next，prev即為屬性

然后需要三個參數，雙向鏈表的前后指針，map，容量

10.兩兩交換鏈表中的節點

1.答案

package com.sunxiansheng.arithmetic.day13;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 24. 兩兩交換鏈表中的節點** @Author sun* @Create 2025/1/19 12:01* @Version 1.0*/
public class t24 {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(0);dummy.next = head;ListNode cur = dummy;// 提前記錄prevListNode prev = dummy;// 循環翻轉while (true) {// 先判斷是否有一組for (int i = 0; i < 2; i++) {if (cur.next == null) {return dummy.next;}cur = cur.next;}// 到這里就是有一組了，開始翻轉ListNode start = prev.next;ListNode then = start.next;reverse(prev, start, then);// 更新prev和curprev = start;cur = prev;}}// 兩個一組翻轉鏈表private void reverse(ListNode prev, ListNode start, ListNode then) {start.next = then.next;then.next = prev.next;prev.next = then;then = start.next;}
}

2.思路

就是兩個一組翻轉鏈表，翻轉鏈表的次數是節點數減一，然后要提前記錄prev，并且在翻轉后更新prev和start

11.環形鏈表 II

1.答案

package com.sunxiansheng.arithmetic.day13;import com.sunxiansheng.arithmetic.util.ListNode;/*** Description: 142. 環形鏈表 II** @Author sun* @Create 2025/1/19 12:31* @Version 1.0*/
public class t142 {public ListNode detectCycle(ListNode head) {// 快慢指針ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {// 這樣只能代表有環，如果想要找到入環的第一個節點，就要讓slow等于head，然后一起移動slow = head;while (slow != fast) {slow = slow.next;fast = fast.next;}return slow;}}return null;}
}

2.思路

發現有環之后，如果想要找到入環的第一個節點，就要讓slow等于head，然后一起移動，直到相遇