LeetCode：链表

160. 相交链表

/*** 单链表的定义* Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode l1 = headA;ListNode l2 = headB;while(l1 != l2){if(l1!=null){l1=l1.next; //指针移动到下一个节点}else{l1=headB;//指针移动到最后，换成另一个链表遍历}if(l2!=null){l2=l2.next;}else{l2=headA;}}return l2;}
}

206. 反转链表

讲解：反转链表【基础算法精讲 06】_哔哩哔哩_bilibili

/*** 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 || head.next==null)return head;//原地调整链表//利用cur、nxt、pre三个新指针ListNode cur = head;ListNode pre = null;while(cur!=null){//nxt指针为当前节点的下一个ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}
}

21. 合并两个有序链表

【从零开始刷LeetCode】第四天：合并两个有序链表（动画演示、手写 Java 代码、详细注释、LeetCode 高频算法题）_哔哩哔哩_bilibili

/*** 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) {if(list1==null) return list2;if(list2==null) return list1;//虚拟头节点ListNode dummy = new ListNode(-1);//虚拟前置指针ListNode pre = dummy;while(list1!=null && list2!=null){if(list1.val <= list2.val){pre.next = list1;list1=list1.next;}else{pre.next = list2;list2=list2.next;}pre = pre.next;}//以防一个链遍历完了，另一个没有遍历完if(list1==null && list2!=null)pre.next=list2;if(list1!=null && list2==null)pre.next=list1;return dummy.next;}
}

83. 删除排序链表中的重复元素

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode cur = head;ListNode pre = new ListNode(-1);pre = head;while(cur!=null && cur.next!=null){if(cur.val==cur.next.val){pre=cur;cur.next=cur.next.next;}else{pre=cur;cur=cur.next;}}return head;}
}

19. 删除链表的倒数第 N 个结点

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode cur = head;ListNode dummy = head;int len=0;while(cur!=null){cur=cur.next;len++;}ListNode newCur = head;for(int i=0; i<len-n-1; i++){newCur=newCur.next;}newCur.next=newCur.next.next;return dummy;}
}
删除链表的倒数第N个节点这道题中，我写的newCur.next=newCur.next.next;
这一句为什么报错？在您提供的代码中，报错的原因可能是因为当您试图删除倒数第N个节点时，
如果N等于链表的长度（即要删除的是头节点），
那么在执行 newCur.next = newCur.next.next; 这一行时，
newCur 实际上可能是 null，因为 len - n - 1 可能为 -1。为了修复这个问题，您应该修改循环条件，并确保在删除节点之前 newCur 不是 null。
以下是修改后的代码：class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode cur = head;int len = 0;// 计算链表长度while (cur != null) {cur = cur.next;len++;}ListNode dummy = new ListNode(0); // 创建一个哑节点，指向头节点dummy.next = head;//头节点可能会被删除，所有用一个dummy作为head的替身，最后返回的不是head，而是dummy.nextListNode newCur = dummy; // 从哑节点开始遍历// 找到要删除节点的前一个节点for (int i = 0; i < len - n; i++) {newCur = newCur.next;}// 删除节点newCur.next = newCur.next.next;return dummy.next; // 返回哑节点的下一个节点，即新的头节点}
}
创建了一个哑节点 dummy，它的 next 指向 head。这样即使删除的是头节点，我们也可以通过 dummy 正确地返回新的头节点。
循环条件从 len - n - 1 改为 len - n，因为我们要找到要删除节点的前一个节点。
返回值从 dummy 改为 dummy.next，这样即使头节点被删除，也能正确返回新的头节点。

24. 两两交换链表中的节点

class Solution {public ListNode swapPairs(ListNode head) {if(head==null || head.next==null) return head;ListNode dummy = new ListNode(-1);dummy.next=head;ListNode pre=dummy;//pre的位置选取是待处理两个节点的前一个
//l1、l2都是在循环里设的
//熟悉过程while(pre.next!=null && pre.next.next!=null){ListNode l1 = pre.next;ListNode l2 = pre.next.next;ListNode nxt = l2.next;pre.next=l2;l2.next=l1;l1.next=nxt;pre=l1;}return dummy.next;}
}

234. 回文链表

class Solution {public boolean isPalindrome(ListNode head) {ListNode mid = findMiddle(head);ListNode list2 = reverseList(mid);while(list2!=null){if(head.val != list2.val){return false;}head=head.next;list2=list2.next;                }return true;}//快慢指针找中点public ListNode findMiddle(ListNode head){ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){slow=slow.next;fast=fast.next.next;}return slow;}//还是反转链表public ListNode reverseList(ListNode head){if(head==null || head.next==null)return head;ListNode pre = null;ListNode cur = head;while(cur!=null){ListNode nxt = cur.next;cur.next = pre;pre = cur;cur = nxt;}return pre;}}

141. 环形链表

public class Solution {public boolean hasCycle(ListNode head) {if(head==null || head.next==null)return false;ListNode slow = head;ListNode fast = head;//存在fast.next.next这种越级调用时，需要确保fast.next不为空while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;if(slow==fast)return true;                       }return false;}
}

142. 环形链表 II

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while(true){if(fast==null || fast.next==null) return null;slow=slow.next;fast=fast.next.next;//定位到两针相遇位置,跳出，此时确定有环if(slow==fast)break;}//此时从head处走到环的开始处 与 从相遇处走到环的开始处 步数一样fast=head;while(fast!=slow){slow=slow.next;fast=fast.next;}return slow;}
}

725. 分隔链表

class Solution {public ListNode[] splitListToParts(ListNode head, int k) {ListNode[] ans = new ListNode[k];if(head==null) return ans;// 遍历链表int len = 0;ListNode cur = head;while (cur != null) {len++;cur = cur.next;}// 计算每组的长度 和 多余的长度int subLen = (len>k) ? (len/k):1;int rest = (len>k) ? (len%k):0;cur = head;int num = 0;while(cur!=null){//每组需要移动的长度int move = subLen + (((rest--)>0)?1:0);for(int i=0; i<move-1; i++){cur=cur.next;}ans[num]=head;head=cur.next;cur.next=null;cur=head;num++;}return ans;}
}

148. 排序链表

【力扣hot100】【LeetCode 148】排序链表｜归并排序的应用_哔哩哔哩_bilibili

class Solution {public ListNode sortList(ListNode head) {if(head==null || head.next==null) return head;ListNode head2 = middleList(head);head = sortList(head);head2 = sortList(head2);return merge(head, head2);}//找链表中点，并断链public ListNode middleList(ListNode head){ListNode dummy = new ListNode(-1);ListNode pre = dummy;ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){//pre=pre.next 不行，有空指针pre=slow;slow=slow.next;fast=fast.next.next;}pre.next=null;return slow;}//两个链表合成有序链表public ListNode merge(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 && list2==null) cur.next=list1;if(list1==null && list2!=null) cur.next=list2;return dummy.next;}
}

138. 随机链表的复制

题解：leetcode上——> 两种实现+图解 138. 复制带随机指针的链

/*
// 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) {if(head==null) return head;Node pre = head;//在每个节点后面设置新节点while(pre!=null){Node newNode = new Node(pre.val, pre.next, null);pre.next=newNode;pre=newNode.next;}pre=head;
//设置新节点的随机random指针while(pre!=null && pre.next!=null){if(pre.random!=null)pre.next.random=pre.random.next;pre=pre.next.next;}Node cur = head;Node dummy = new Node(-1);pre=dummy;//设法将新旧两个链表分开while(cur!=null){pre.next=cur.next;pre=pre.next;cur.next=pre.next;cur=cur.next;           }return dummy.next;}
}

146. LRU 缓存

class LRUCache {private static class Node {Node pre, next;int key, value;// 构造器Node(int key, int value) {this.key = key;this.value = value;}}private final int capacity;private final Node dummy = new Node(0, 0);private final Map<Integer, Node> keyToNode = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;dummy.next = dummy;dummy.pre = dummy;}public int get(int key) {Node node = getAndFront(key);if (node == null) {return -1;}return node.value;}//易错处public void put(int key, int value) {// 如果key的node存在Node node = keyToNode.get(key);if (node != null) {node.value = value;remove(node);addFront(node);return;}// 这个key不存在，新建nodenode = new Node(key, value);addFront(node);keyToNode.put(key, node);if (keyToNode.size() > capacity) {// 从表尾删除一个节点Node lastNode = dummy.pre;keyToNode.remove(lastNode.key);remove(lastNode);}}// 以上的put和get应基于以下几个基础操作// 删除节点public void remove(Node x) {x.pre.next = x.next;x.next.pre = x.pre;}// 从链表头插入public void addFront(Node x) {x.pre = dummy;dummy.next.pre = x;x.next = dummy.next;dummy.next = x;}// 用key get某个节点，并把节点移到链表头部public Node getAndFront(int key) {if (!keyToNode.containsKey(key))return null;Node node = keyToNode.get(key);remove(node);addFront(node);return node;}
}

2. 两数相加

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0); // 辅助节点ListNode pre = dummy;//进位carryint carry=0;while(l1!=null || l2!=null){if(l1!=null){carry += l1.val;l1=l1.next;}if(l2!=null){carry += l2.val;l2=l2.next;}//新节点是carry的个位数pre.next = new ListNode(carry%10);pre = pre.next;//判断是否有进位carry = (carry>=10)?1:0;}//最后循环结束，如果有进位，还需要补上最后一个1（这个1是最高位的1）if(carry==1){pre.next = new ListNode(carry);}return dummy.next;}
}

25. K 个一组翻转链表(⭐)

【LeetCode 每日一题】25. K 个一组翻转链表 | 手写图解版思路 + 代码讲解_哔哩哔哩_bilibili

class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode dummy = new ListNode(-1, head);ListNode start_pre = dummy;ListNode end = dummy;while(true){//遍历end，至本组最后一个节点for(int i=0; i<k&&end!=null; i++)end=end.next;if(end==null) break;//start为本组第一个节点ListNode start = start_pre.next;//endNxt为下一组的最后一个节点ListNode endNxt = end.next;//翻转之前把链断掉end.next=null;//翻转本组节点start_pre.next = reverse(start);//翻转之后，本组的尾部去接下一组的头部start.next=endNxt;//调整各个指针位置end = start;start_pre = start;}return dummy.next;}public ListNode reverse(ListNode head){ListNode pre = null;ListNode cur = head;while(cur!=null){ListNode nxt = cur.next;cur.next=pre;pre=cur;cur=nxt;}return pre;}
}

23. 合并 K 个升序链表（hard）

迭代法

class Solution {public ListNode mergeKLists(ListNode[] lists) {int n = lists.length;if (n == 0) return null;while(n>1){//index每次都初始化为0，因为要在lists的开头来存放合并出来的临时结果int index = 0;for(int i=0; i<n; i+=2){ListNode l1 = lists[i];ListNode l2 = null;if(i+1<n)l2 = lists[i+1];lists[index++] = mergeTwoLists(l1, l2);}//index是lists数组新的长度n = index;}return lists[0];}

递归法

/*** 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) {if (lists.length == 0) return null;return merge(lists, 0, lists.length-1);}//递归法public ListNode merge(ListNode[] lists, int low, int high){if(low==high)return lists[low];int middle = low + (high-low)/2;ListNode l1 = merge(lists, low, middle);ListNode l2 = merge(lists, middle+1, high);return mergeTwoLists(l1, l2);}//合并两个有序链表public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null && list2 == null)return null;if (list1 == null || list2 == null)return (list1 == null) ? list2 : list1;ListNode dummy = new ListNode(-1);ListNode pre = dummy;while (list1 != null && list2 != null) {if (list1.val < list2.val) {pre.next = list1;list1 = list1.next;} else {pre.next = list2;list2 = list2.next;}pre = pre.next;}if (list1 != null)pre.next = list1;if (list2 != null)pre.next = list2;return dummy.next;}
}