leetcode啟動！(╯‵□′)╯︵┻━┻
嘗試改掉想到哪寫哪的代碼壞習慣

鏈表
相交鏈表

public class Solution {/**ac（公共長度）b所以 鏈表A的長度 a + c，鏈表B的長度b + ca + b + c = b + c + a只要指針a從headA開始走，走完再回到headB指針b從headB開始走，走完回到headA兩個指針相遇的地方一定是鏈表交點*/public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pA = headA;ListNode pB = headB;while(pA != pB) {pA = (pA == null) ? headB : pA.next;pB = (pB == null) ? headA : pB.next;}return pA;}
}

反轉鏈表

class Solution {/**設置一個null結點pre作為反轉后的尾結點curr結點一路向后遍歷因為要改變結點指向，所以需要用temp保存curr下一個結點開寫~*/public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

回文鏈表

class Solution {/**反轉鏈表，和舊鏈表逐個元素比較主打一個耗時耗力*/public boolean isPalindrome(ListNode head) {ListNode pre = null;ListNode cur = head;ListNode copy = head;ListNode old = new ListNode(head.val);ListNode oldList = old;while(copy != null) {// System.out.println(copy.val);copy = copy.next;if(copy != null) {ListNode temp = new ListNode(copy.val);old.next = temp;old = old.next;}}old.next = null;while(cur != null) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}ListNode newList = pre;while(newList != null) {if(newList.val != oldList.val) {return false;}newList = newList.next;oldList = oldList.next;}return true;}
}

環形鏈表

public class Solution {/**使用快慢指針slow一次走一步，fast一次走兩步快慢指針一定會在環內相遇,記為meet點這個時候slow從head開始走，meet從相遇點開始走，兩者一定會在環入口相遇*/public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;ListNode connect = null;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow == fast) {connect = slow;return true;}}return connect == null ? false : true;}
}

環形鏈表II

public class Solution {/**原來上一題的判斷寫成了這一題的找環的入口思路一樣接著上一題找到meet點此時只要slow再次從頭開始走，meet指針向后走，兩者就一定會在環入口處相遇*/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) {ListNode meet = slow;slow = head;while(slow != meet) {slow = slow.next;meet = meet.next;}return slow;}}return null;}
}

合并兩個有序鏈表

class Solution {/**樸實無華的想法新建一個頭結點null，進行結點挑選list1.val > list2.val ? 好，挑list2的結點來復制list1.val <= list2.val ? 好，挑list1的結點來復制如果list1或者list2走到頭了，就直接選擇不空的一連（因為已經排好序了）需要注意的是，所有的情況用if-else分好，否則會執行出錯*/public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p = new ListNode(-1);ListNode res = p;while(list1 != null || list2 != null) {if(list1 == null) {p.next = list2;return res.next;}else if(list2 == null) {p.next = list1;return res.next;}else {if(list1.val > list2.val) {ListNode temp = new ListNode(list2.val);p.next = temp;p = p.next;list2 = list2.next;}else {ListNode temp = new ListNode(list1.val);p.next = temp;p = p.next;list1 = list1.next;}}}return res.next;}
}

兩數相加
（什么破代碼又臭又長 (┙>∧<)┙へ┻┻）

import java.math.BigInteger;
class Solution {/**樸實無華的想法，逆序想到棧道先進后出功能，使用棧保存數據時間空間效率你是一點不考慮啊苦路西測試用例有超出Long范圍的，需要BigIntegerBigInteger b1 = new BigInteger("2020031920200319");BigInteger b2 = new BigInteger("2020031820200318");//加法BigInteger add = b1.add(b2);System.out.println(add);//減法BigInteger subtract = b1.subtract(b2);System.out.println(subtract);//乘法BigInteger multiply = b1.multiply(b2);System.out.println(multiply);//除法BigInteger divide = b1.divide(b2);System.out.println(divide);*/public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Stack<Integer> stack = new Stack();int count1 = 0;ListNode p1 = l1;while(p1 != null) {stack.push(p1.val);p1 = p1.next;count1++;}BigInteger sum1 = new BigInteger("0");BigInteger base = BigInteger.TEN;while(!stack.isEmpty()) {int temp = stack.pop();count1--;BigInteger tempAsBigInteger = BigInteger.valueOf(temp);BigInteger ten = base.pow(count1);BigInteger mul = tempAsBigInteger.multiply(ten);sum1 = sum1.add(mul);}int count2 = 0;ListNode p2 = l2;while(p2 != null) {stack.push(p2.val);count2++;p2 = p2.next;}BigInteger sum2 = new BigInteger("0");while(!stack.isEmpty()) {int temp = stack.pop();count2--;BigInteger tempAsBigInteger = BigInteger.valueOf(temp);BigInteger ten = base.pow(count2);BigInteger mul = tempAsBigInteger.multiply(ten);sum2 = sum2.add(mul);}System.out.println(sum1);System.out.println(sum2);BigInteger sum = new BigInteger("0");sum = sum1.add(sum2);System.out.println(sum);ListNode res = new ListNode(0);ListNode r = res;if((sum.compareTo(BigInteger.ZERO)) == 0) {return r;}while((sum.compareTo(BigInteger.ZERO)) != 0) {BigInteger x = sum.mod(base);// System.out.println(x);int x1 = x.intValue();// System.out.println(x1);ListNode temp = new ListNode((int)x1);res.next = temp;res = res.next;sum  = sum.divide(base);}return r.next;}
}

刪除鏈表點倒數第N個結點

class Solution {/**快指針fast先走N布然后慢指針slow從頭開始，和fast一起走，當fast走到頭了，slow在的位置就是要刪除的位置1 - 2 - 3 - 4 - null-2   1   0--       --        -刪        */public ListNode removeNthFromEnd(ListNode head, int n) {ListNode p = new ListNode(-1);p.next = head;ListNode res = p;ListNode fast = p;ListNode slow = p;while(n > 0) {n--;fast = fast.next;}while(fast.next != null) {slow = slow.next;fast = fast.next;}slow.next = slow.next.next;return p.next;}
}

兩兩交換鏈表結點

class Solution {/**-1 - 1 - 2 - 3 - 41 保存一下pre-1 - 2 - 3 - 43 - 4 保存一下after-1 - 2 - 1-1 - 2 - 1 - 3 - 4*/public ListNode swapPairs(ListNode head) {ListNode p = new ListNode(-1);ListNode res = p;p.next = head;while(p.next != null && p.next.next != null) {ListNode pre = p.next;p.next = p.next.next;ListNode after = p.next.next;p.next.next = pre;pre.next = after;p = pre;}return res.next;}
}

K個一組鏈表反轉

class Solution {/**只需要想遞歸最后一次null <- 2 <- 1  3 -> 4 -> 5 -> null2.next = reverseGroup(., k)*/public ListNode reverseKGroup(ListNode head, int k) {if(head == null) {return null;}ListNode a = head;ListNode b = head;for(int i = 0; i < k; i++) {if(b == null) {return head;}b = b.next; // 判斷要在指針后移之前啊啊啊啊}// 一開始用的while k--, 忘了把k從0恢復ListNode newHead = reverseKNodes(a, b);a.next = reverseKGroup(b, k);return newHead;}public ListNode reverseKNodes(ListNode a, ListNode b) {ListNode pre = null;ListNode cur = a;while(cur != b) {ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;}
}

隨機鏈表的復制

class Solution {/**感覺和拷貝鏈表沒有什么區別多了個random嘛, 用hashmap存*/public Node copyRandomList(Node head) {Node h = head;HashMap<Node, Node> map = new HashMap<>();Node newHead = new Node(-1);Node h1 = newHead;while(h != null) {Node temp = new Node(h.val);map.put(h, temp);newHead.next = temp;newHead = newHead.next;h = h.next;}h = head;Node h2 = h1.next;while(h != null) {h2.random = map.get(h.random);h = h.next;h2 = h2.next;}return h1.next;}
}

排序鏈表

class Solution {/**樸實無華的想法用List存鏈表元素，Collections.sort()進行排序，再新建一個鏈表*/public ListNode sortList(ListNode head) {List<Integer> list = new ArrayList();ListNode h = head;ListNode sortedList = new ListNode(-1);ListNode res = sortedList;while(h != null) {list.add(h.val);h = h.next;}Collections.sort(list);for(int i = 0; i < list.size(); i++) {ListNode temp = new ListNode(list.get(i));sortedList.next = temp;sortedList = sortedList.next;}return res.next;}
}

合并K個有序鏈表

class Solution {/**使用最小堆注意：lists是一個數組，是用lists.length獲取長度*/public ListNode mergeKLists(ListNode[] lists) {if(lists.length == 0) {return null;}ListNode p = new ListNode(-1);ListNode res = p;PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a,b) -> (a.val - b.val));for(ListNode head :lists) {if(head != null) {pq.add(head);}}while(!pq.isEmpty()) {ListNode node = pq.poll();p.next = node;if(node.next != null) {pq.add(node.next);}p = p.next;}return res.next;}
}

LRU緩存

class LRUCache {/**八股問過，內存淘汰策略，刪除存活時間最久的keyallkesy-lru*/int cap;LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();public LRUCache(int capacity) {this.cap = capacity;}public int get(int key) {if(!cache.containsKey(key)) {return -1;}makeRecently(key);return cache.get(key);}public void put(int key, int val) {if(cache.containsKey(key)) {cache.put(key, val);makeRecently(key);return;}if(cache.size() >= this.cap) {int oldestKey = cache.keySet().iterator().next();cache.remove(oldestKey);}cache.put(key, val);}private void makeRecently(int key) {int val = cache.get(key);cache.remove(key);cache.put(key, val);}
}