基于合并有序链表思路三个题
21. 合并两个有序链表 - 力扣（LeetCode）
虚拟头节点起始，dh指向虚拟头，用尾插法插入较小节点，最后补上剩余的链表，因为链表有序。
class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head = new ListNode(0); ListNode dh = head; while(list1 != null && list2 != null){ if(list1.val <= list2.val){ dh.next = list1; list1 = list1.next; }else{ dh.next = list2; list2 = list2.next; } dh = dh.next; } if(list1 != null){ dh.next = list1; }else{ dh.next=list2; } return head.next; } }148. 排序链表 - 力扣（LeetCode）
基于递归归并排序把中点两侧排序，然后基于合并有序链表的思路合并，空间复杂度为logn，时间为nlogn。
找中点：注意fast要在slow后面，保证偶数个时候不会无限循环
/** * 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 sortList(ListNode head) { if(head == null||head.next==null) return head; ListNode fast = head.next; ListNode slow = head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } ListNode left=head; ListNode right = slow.next; slow.next=null; ListNode leftSort= sortList(head); ListNode rightSort = sortList(right); return mergeTwoLists(leftSort,rightSort); } public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head = new ListNode(0); ListNode dh = head; while(list1 != null && list2 != null){ if(list1.val <= list2.val){ dh.next = list1; list1 = list1.next; }else{ dh.next = list2; list2 = list2.next; } dh = dh.next; } if(list1 != null){ dh.next = list1; }else{ dh.next=list2; } return head.next; } }23. 合并 K 个升序链表 - 力扣（LeetCode）
基于归并排序和有序链表合并的思路，递归处理每个链表
注意递归的终止条件和判空。
class Solution { public ListNode mergeKLists(ListNode[] lists) { if(lists.length==0||lists==null)return null; return sortList(lists, 0, lists.length-1); } public ListNode sortList(ListNode[] lists, int left, int right){ if(left==right) return lists[left]; int mid = (right+left)/2; ListNode leftNode = sortList(lists, left, mid); ListNode rightNode = sortList(lists, mid+1, right); return mergeTwoLists(leftNode, rightNode); } public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode head = new ListNode(0); ListNode dh = head; while(list1 != null && list2 != null){ if(list1.val <= list2.val){ dh.next = list1; list1 = list1.next; }else{ dh.next = list2; list2 = list2.next; } dh = dh.next; } if(list1 != null){ dh.next = list1; }else{ dh.next=list2; } return head.next; } }反转链表系列：
206. 反转链表 - 力扣（LeetCode）
25. K 个一组翻转链表 - 力扣（LeetCode）
定义反转链表的普通方法
prev：已经处理好的链表的尾节点。初始指向dummy。cur：从prev出发，向后走 k 步，到达当前待处理组的第 k 个节点（即这一组的尾部）。nextStart：cur.next，即剩余未处理链表的头部（下一组的起点groupHead代表当前待处理链表的头部，fanzhuanRes反转后的新头，
注意反转之后的重新连接。
剩余不足 k 个的节点不需要反转，也不需要额外处理，这部分剩余节点已经通过前一组的尾节点连接到了结果链表中，并且保持了原有的顺序
class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dim = new ListNode(-1); dim.next = head; ListNode prev = dim; while(true){ ListNode cur = prev; for(int i = 0; i <k && cur !=null;i++){ cur = cur.next; } if(cur==null) break; ListNode nextStart = cur.next; cur.next=null; ListNode groupHead = prev.next; ListNode fanzhuanRes= fanzhuan(groupHead); prev.next = fanzhuanRes; prev = groupHead; groupHead.next = nextStart; } return dim.next; } ListNode fanzhuan(ListNode node){ ListNode prev = null; ListNode cur = node;; while(cur != null){ ListNode next = cur.next; cur.next = prev; prev = cur; cur = next; } return prev; } }环形链表：
141. 环形链表 - 力扣（LeetCode）
快慢指针都在head，注意快指针的终止条件
public class Solution { public boolean hasCycle(ListNode head) { if(head==null || head.next==null)return false; ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast=fast.next.next; slow=slow.next; if(slow==fast) return true; } return false; } }142. 环形链表 II - 力扣（LeetCode）
head ──a──> 入口 ──b──> 相遇点 ↑ │ └──── c ─────┘
slow:a+b
fast:a+b+n(b+c)
a+b+n(b+c) = 2 (a+b)
a = (n-1)(b+c)+c
注意点：无环的时候判断fast为空或者next为空都返回空
最后找入口点的时候，代码中不显式写圈数，靠 slow交点位置在环上自然行走来“绕圈”。
public class Solution { public ListNode detectCycle(ListNode head) { if(head==null || head.next==null)return null; ListNode fast=head; ListNode slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(slow==fast) break; } if(fast==null || fast.next==null) return null; while(head!=slow){ head=head.next; slow=slow.next; } return slow; } }普通链表题：
146. LRU 缓存 - 力扣（LeetCode）
哈希表：存储key+节点地址
双向链表：包含头尾指针，便于增加和删除，找到前驱后继
哈希的value组成双链表，定义头部为最近使用，尾部为最近不使用
注意两个错误：
get之后要把当前节点删除，搬到头节点后
put覆盖之后要把当前节点删除，搬到头节点后。
class LRUCache { class Node { int key,val; Node prev, next; Node(int key, int val){ this.key=key; this.val=val; } } int capacity; HashMap<Integer, Node> map; Node head, tail; public LRUCache(int capacity) { this.capacity=capacity; map = new HashMap<>(); head=new Node(0,0); tail=new Node(0,0); head.next=tail; tail.prev=head; } public int get(int key) { if(!map.containsKey(key)){ return -1; } Node node=map.get(key); remove(node); addToHead(node); return node.val; } public void put(int key, int value) { if(map.containsKey(key)){ Node cur = map.get(key); cur.val=value; remove(cur); addToHead(cur); }else{ if(map.size()==capacity){ Node deleNode = tail.prev; remove(deleNode); map.remove(deleNode.key); } Node node=new Node(key, value); map.put(key, node); addToHead(node); } } void remove(Node node){ node.prev.next = node.next; node.next.prev = node.prev; } void addToHead(Node node){ node.next=head.next; node.prev=head; head.next=node; node.next.prev=node; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */138. 随机链表的复制 - 力扣（LeetCode）
简单思路：哈希表存储节点的副本节点
class Solution { public Node copyRandomList(Node head) { HashMap<Node, Node> map = new HashMap<>(); Node cur = head; // a->a' while(cur != null){ map.put(cur, new Node(cur.val)); cur=cur.next; } cur=head; //a'.next=(a.next)' while(cur!=null){ map.get(cur).next=map.get(cur.next); map.get(cur).random=map.get(cur.random); cur=cur.next; } return map.get(head); } }24. 两两交换链表中的节点 - 力扣（LeetCode）
和k个一组翻转类似，dummy 节点 + prev/cur/aft 三指针
换序+prev和cur、aft位置搬运
ListNode aft = cur.next.next; // 备份剩余链表头
prev.next = cur.next; // ┐
cur.next.next = cur; // ├ 三步完成换序 + 接回
cur.next = aft; // ┘
prev = cur; // ┐
cur = aft; // ┘ 两步移动指针
class Solution { public ListNode swapPairs(ListNode head) { if(head==null||head.next==null) return head; ListNode dim = new ListNode(0,head); ListNode prev = dim; ListNode cur = head; while(cur != null && cur.next != null){ ListNode aft = cur.next.next; prev.next = cur.next; cur.next.next = cur; cur.next = aft; prev = cur; cur = aft; } return dim.next; } }19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
容易错：虚拟节点加上，返回不能直接返回head，fast先走的步数是n+1
fast先走n+1步，再同时走，fast还需要len-n步停止，slow走len-n步，还剩余n个节点，正好到达倒数第n+1个节点处
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head.next==null)return null; ListNode dum = new ListNode(-1); dum.next=head; ListNode fast = dum; ListNode slow = dum; for(int i=0;i<n+1;i++){ fast=fast.next; } while(fast!=null){ fast=fast.next; slow=slow.next; } slow.next = slow.next.next; return dum.next; } }2. 两数相加 - 力扣（LeetCode）
三种情况需要循环：
l1还有节点l2还有节点carry还有进位
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int jinwei =0; ListNode dumHead = new ListNode(-1); ListNode prev = dumHead; while(l1 != null || l2 !=null || jinwei > 0){ int x = l1 != null ? l1.val : 0; int y = l2 != null ? l2.val : 0; int curval = jinwei+x+y; jinwei = curval /10; int gewei = curval % 10; prev.next = new ListNode(gewei); prev = prev.next; if(l1 !=null) l1 = l1.next; if(l2 !=null) l2 = l2.next; } return dumHead.next; } }
