中等
160. 相交链表【中等】
学习：leetcode题解
题目链接：160. 相交链表
题目内容：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
速记：
①首先求得两个链表的长度，根据长度差值将长的指针向后移动，直至两个链表从相同长度开始来进行一一比较得出相交结点。 ②使用哈希表来先存储链表A的所有节点，接着对链表B进行遍历，若是B的某个节点在哈希表中存在，那么就说明相交。 ③使用两个指针来同时遍历两个链表，两个指向指向的节点是否相等作为条件，若是某个链表先遍历完了还没找到，那么就让该节点从新的链表出发，另一个节点同理。最终只有两种情况，①相交。②无相交，最终同时会指向null结束。
思路：
1、同步后缀比较
思路：首先求得两个链表的长度，根据长度差值将长的指针向后移动，直至两个链表从相同长度开始来进行一一比较得出相交结点。
复杂度分析：时间复杂度O(n)，空间复杂度O(1)
class Solution { /** * 获取链表的长度 * @param node * @return */ public int getListNodeSize(ListNode node){ int size = 0; while (node != null){ size++; node = node.next; } return size; } public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null){ return null; } //确定链表的长度 int aSize = getListNodeSize(headA); int bSize = getListNodeSize(headB); //移动节点少的链表，让其成为相同长度的链表 int moveSize = Math.abs(aSize-bSize); if(aSize < bSize){ while (moveSize-- > 0){ headB = headB.next; } }else if(aSize > bSize){ while (moveSize-- > 0){ headA = headA.next; } } //开始正式比对 while(headA != null){ if(headA == headB){ return headA; } headA = headA.next; headB = headB.next; } return null; } }
2、哈希集合
思路：首先将链表A的节点全部存储到哈希集合中，之后遍历链表B来查看在哈希集合中是否存在对应的节点A。
复杂度分析：时间复杂度O(m+n)，空间复杂度O(m)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null){ return null; } Set<ListNode> nodes = new HashSet<>(); while (headA != null){ nodes.add(headA); headA = headA.next; } //遍历headB链表，来判断是否有相交的节点 while (headB != null){ if(nodes.contains(headB)){ return headB; } headB = headB.next; } return null; }
3、双指针
思路：两个链表长度分别为m、n。两个链表同时从头节点出发，若是先碰到节点，则将该指针指到另一个链表的头节点继续两个指针向后移动，另外一个节点也是如此。最终会有两个结果：①没有交点，最终都会为null，直接结束。②有交点，两个节点相等。
复杂度分析：时间复杂度O(m+n)，空间复杂度O(1)
class Solution { //双指针思路 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null){ return null; } ListNode pA = headA; ListNode pB = headB; //最终会有两种情况：①没有交点，最终都会为null，直接结束。②有交点，两个节点相等。 while(pA != pB){ pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } }
2. 两数相加【中等】
学习：leetcode题解
题目链接：2. 两数相加
题目内容：
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
思路：
1、模拟（虚拟头节点）
思路：定义虚拟头节点，接着两个链表进行统一位置值相加，过程中需要使用一个temp来保存是否/10的结果(即进一)。
复杂度分析：时间复杂度O(max(m,n))、空间复杂度O(1)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode root = new ListNode(-1); ListNode cur = root; int temp = 0; while (l1 != null && l2 != null) { int sum = temp + l1.val + l2.val; cur.next = new ListNode(sum % 10); cur = cur.next; temp = sum / 10; l1 = l1.next; l2 = l2.next; } //将剩余节点进行补充 fillListNode(l1, cur, temp); fillListNode(l2, cur, temp); //两个链表相同长度 if (l1 == null && l2 == null && temp == 1) { cur.next = new ListNode(1); } return root.next; } public void fillListNode(ListNode node,ListNode cur,int temp){ if (node == null){ return; } while (node != null){ int sum = temp + node.val; cur.next = new ListNode(sum % 10); cur = cur.next; temp = sum / 10; node = node.next; } if (temp == 1) { cur.next = new ListNode(1); } }
2、模拟（优化代码）
思路：与NO1思路一致，只不过这里并没有定义虚拟头节点，代码结构也更加清晰。
复杂度分析：时间复杂度O(max(m,n))、空间复杂度O(1)
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int temp = 0; ListNode head = null, tail = null; while (l1 != null || l2 != null) { //取得两个链表的当前位置的值 int val1 = l1 != null ? l1.val : 0; int val2 = l2 != null ? l2.val : 0; int sum = temp + val1 + val2; //头节点构造情况及之后尾部添加 if (head == null) { head = tail = new ListNode(sum % 10); }else{ tail.next = new ListNode(sum % 10); tail = tail.next; } //保存十位数位置值(是否进1) temp = sum / 10; if (l1 != null){ l1 = l1.next; } if (l2 != null){ l2 = l2.next; } } if (temp > 0) { tail.next = new ListNode(temp); } return head; }
奇偶链表【中等】
链接地址：328. 奇偶链表
题目描述：给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
方式一：奇偶链表，寻路链表，最后拼接
//方式一：定义奇、偶数链表，使用导航节点来进行指引奇、偶节点进行连接，最后将偶数链表连接到奇数链表末尾返回。 /** * 时间复杂度O(n)、空间复杂度O(1) * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 * 内存消耗：40.5 MB, 在所有 Java 提交中击败了91.77%的用户 */ public ListNode oddEvenList(ListNode head) { //若是节点数为0或者1直接返回 if (head == null || head.next == null) { return head; } //定义奇数节点、偶数节点。对于head节点不动，tail节点不断向后移动 ListNode oddHead = head; ListNode oddTail = oddHead; ListNode evenHead = head.next; ListNode evenTail = evenHead; //定义一个导航节点 ListNode p = head.next.next; while (p != null) { //先尝试连接奇数链表 oddTail = oddTail.next = p; p = p.next; if (p != null) { //连接偶数链表 evenTail = evenTail.next = p; p = p.next; } } //将偶数链表连接到奇数链表末节点之后 oddTail.next = evenHead; evenTail.next = null;//奇数链表末尾是null return oddHead; }
707. 设计链表【中等】
学习：代码随想录—707.设计链表、leetcode评论
题目链接：707. 设计链表
题目内容：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能： get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。 addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。 addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。 addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
注意：
①注意下面这句话，第 index 个节点之前添加值为 val 的节点实际上与后面等于链表的长度不冲突，只需要把等于条件放在前面即可。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
②注意点(坑点)：红框勾选的一个是获取，一个是删除，注意题目写的是获取或删除第index个节点，从字面上来看传入1，就是删除掉链表中的第一个元素，而实际上则是需要你删除或获取到索引为index的元素。
思路：
1、手写链表
看题先自己尝试手写并。期间有N次提交失败，还有空指针异常情况，主要就是我们上面二大注意点提到的，经过一些时间终于AC！
class MyLinkedList { private ListNode head;//头节点 private ListNode tail;//尾结点 private int size;//节点数量 class ListNode{ private int val; private ListNode next; public ListNode(int val,ListNode next) { this.val = val; this.next = next; } } public MyLinkedList() { this.size = 0; } /** * 取的是索引 * @param index * @return */ public int get(int index) { if(!checkExists(index)){ return -1; } //遍历链表 ListNode cur = this.head; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; } public void addAtHead(int val) { ListNode newHead = new ListNode(val, this.head); //更新尾结点 if(this.tail == null){ this.tail = newHead; } //更新头节点 this.head = newHead; this.size++; } public void addAtTail(int val) { ListNode newTail = new ListNode(val, null); //更新尾结点 this.tail = newTail; //处理无头节点情况 if(this.head == null){ this.head = newTail; }else{ //遍历到尾节点插入 ListNode cur = this.head; for (int i = 0; i < this.size-1; i++) { cur = cur.next; } cur.next = newTail; } this.size++; } public void addAtIndex(int index, int val) { //情况1：index>size，不插入节点 if(index > this.size){ return; } //情况2：index<0，在头部插入节点（包含index=0情况） if(index <= 0){ this.addAtHead(val); return; } //情况3：index=size，添加到链表末尾 if(index == this.size){ this.addAtTail(val); return; } //最终情况：在指定index位置前插入 ListNode newNode = new ListNode(val, null); ListNode pre = this.head; //当前数量>1，index>1情况，找到前置节点 for (int i = 1; i < index; i++) { pre = pre.next; } //插入节点操作 newNode.next = pre.next; pre.next = newNode; this.size++; } public void deleteAtIndex(int index) { if(!checkExists(index)){ return; } //情况1：index=0情况 if(index == 0){ this.head = this.head.next; if(size == 1){ this.tail = null; //若是当前数量也为1，尾节点也要删除 } this.size--; return; } //定位到要删除的指定节点前一个 ListNode cur = head; for (int i = 1; i < index; i++) { cur = cur.next; } //判断是否是尾节点，是的话更新尾节点 if(cur.next == this.tail){ this.tail = cur; }else{ //删除指定节点 cur.next = cur.next.next; } this.size--; } public boolean checkExists(int index){ if(index < 0 || index >= size){ return false; } return true; } }
2、双向链表
案例参考leetcode题解的某个评论：我是理解了jdk-8 LinkedList源码写出来的 有不对的地方，希望指正
使用双向链表的话其实就更加轻松一点，并且在本案例中对于方法重用的设计也更加巧妙！
class MyLinkedList { private class Node{ public int val; public Node next; public Node prev; Node(int val){ this.val = val; } Node(Node prev,int val,Node next){ this.prev = prev; this.val = val; this.next = next; } } //头节点 private Node first; //尾结点 private Node last; //链表长度 private int size; public MyLinkedList() { this.first = null; this.last = null; this.size = 0; } public boolean checkIndex(int index){ if(index<0 || index>=size){ return false; } return true; } public int get(int index) { if(!checkIndex(index)){ return -1; } if(index == 0){ return this.first.val; }else if(index == this.size-1){ return this.last.val; }else{ return indexOf(index).val; } } private Node indexOf(int index) { //判断当前索引在链表中的大致位置，若是在左边优先从头节点遍历 if(index < size>>1 ){ Node cur = this.first; for (int i = 0; i < index; i++) { cur = cur.next; } return cur; }else{//从后向前遍历 Node cur = this.last; for (int i = 1 ;i< this.size-index; i++) { cur = cur.prev; } return cur; } } public void addAtHead(int val) { //记录保存一下当前的第一个节点 Node f = this.first; Node newNode = new Node(null, val, f); this.first = newNode;//更新一下头节点 //如果原本第一个节点为null，说明原本链表为空，此时尾结点也肯定为空 if(f == null){ this.last = newNode; }else{ f.prev = newNode;//原本的前置节点进行更新 } this.size++; } public void addAtTail(int val) { //记录保存一下当前的尾节点 Node l = this.last; Node newNode = new Node(l, val, null); this.last = newNode;//更新一下尾节点 if(l == null){ this.first = newNode; }else{ l.next = newNode;//更新一下当前头节点 } this.size++; } public void addAtIndex(int index, int val) { if(index == 0){ this.addAtHead(val); }else if(index == this.size){ this.addAtTail(val); }else if(index>this.size){ return; }else{ //此时index是在当前链表必存在的情况 add(index,val); } } public void add(int index, int val) { Node cur = indexOf(index); Node preNode = cur.prev; Node newNode = new Node(preNode, val, cur); //更新索引为index节点的后置节点为新节点 preNode.next = newNode; cur.prev = newNode; this.size++; } public void deleteAtIndex(int index) { if(!checkIndex(index)){ return; } //当前节点数量=1情况 if(this.size == 1){ this.size--; this.first = null; this.last = null; return; } //当前节点数量>1情况：找到指定要删除的节点 Node delNode = indexOf(index); //删除节点为头节点情况 if(index == 0){ this.first = delNode.next; this.first.prev = null; }else if(index == this.size-1){//为尾结点情况 this.last = this.last.prev; this.last.next = null; }else{ //中间情况，前后节点都要进行更新 delNode.prev.next = delNode.next; delNode.next.prev = delNode.prev; } this.size--; } }
24. 两两交换链表中的节点【中等】
学习：leetcode题解、 代码随想录—24. 两两交换链表中的节点
题目链接：24. 两两交换链表中的节点
题目内容：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路：
1、三指针移动
思路：定义三个指针，每次两两交换后，统一移动三个指针，中间可能会比较绕一点，可搭配画图进行题解。
核心其实就是不断移动三个指针，之后来进行两两交换操作，中间注意一些边界条件即可。
public ListNode swapPairs(ListNode head) { //1个或0个节点直接返回 if(head == null || head.next == null){ return head; } //三个指针 ListNode preNode = null; ListNode firstNode = head; ListNode secNode = firstNode.next; //最终返回的头节点 ListNode newHead = secNode; //只有成对的才能够进行下面的操作 while(firstNode !=null && secNode != null){ //保存secNode的后一个节点 ListNode postNode = secNode.next; //反转节点 secNode.next = firstNode; firstNode.next = postNode; if(preNode!=null){ preNode.next = secNode; } //移动三个指针 preNode = firstNode;//第一个指针 if(postNode == null){ break; } firstNode = postNode;//第二个指针 if(postNode.next == null){ break; } secNode = postNode.next; } return newHead; }
2、虚拟头结点
思路：定义一个虚拟节点后，之后的操作都是相同的，其中核心是以两个指针来进行节点之间的交换。
public ListNode swapPairs(ListNode head) { //虚拟节点 ListNode dummyNode = new ListNode(0, head); ListNode preNode = dummyNode; //该条件含义指的是：保证当前还有成对的进行反转。下面主要核心就是通过preNode、head两个指针来进行两两反转 while(preNode.next != null && preNode.next.next != null){ //临时保存第3个节点，之后反转链表指向第3个节点时有用 ListNode tempNode = head.next.next; //反转链表节点 preNode.next = head.next; head.next.next = head; head.next = tempNode; //移动指针 (注意此时的head与已反转) preNode = head; head = preNode.next; } return dummyNode.next; }
3、递归求解
思路：下面针对于递归题解进行部分问题解答
/** * 递归 * @param head * @return 上一组交换的下一个目标节点 */ public ListNode swapPairs(ListNode head) { if(head == null || head.next == null){ return head; } ListNode next = head.next; ListNode newNode = swapPairs(next.next); //反转链表，只负责当前两个节点指向 next.next = head; head.next = newNode; return next; }
困难
K 个一组翻转链表【困难】
【LeetCode 25. K 个一组翻转链表】 每天一题刷起来！C++ 年薪冲冲冲！
链接地址：25. K 个一组翻转链表
题目描述：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
思路解法：反转链表的进阶版，实际上就是遍历一遍的过程中每根据k个来进行翻转一下，在这里一定要定义一个虚拟头节点，并且在过程中需要使用一些额外的其他节点。
方式一：非递归反转
/** * 时间复杂度O(n)，空间复杂度O(1) * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户 * 内存消耗：40.7 MB, 在所有 Java 提交中击败了83.91%的用户 */ //示例：[1,2,3,4,5] 2 public ListNode reverseKGroup(ListNode head, int k) { if (k <=1 || head == null || head.next == null ) { return head; } ListNode dummy = new ListNode(0);//虚拟头节点 dummy.next = head; ListNode pre = dummy; ListNode cur = head; while (cur != null) { ListNode tail = cur; for (int i = 0; i < k; i++) { if (tail != null) { tail = tail.next; }else { return dummy.next; } } //找到尾节点 pre.next = reverse(cur, tail); cur.next = tail; pre = cur; cur = tail; } return dummy.next; } //反转指定范围的链表 public ListNode reverse(ListNode head,ListNode tail) { if (head == null || head.next == null) { return head; } ListNode pre = null; ListNode cur = head; while (cur != tail) { ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; }
合并K个排序链表【困难】
相同题目：23. 合并K个升序链表
链接地址：剑指 Offer II 078. 合并排序链表
题目描述：请将所有升序排序的链表合并到一个升序链表中，返回合并后的链表。
方式一：一一比较法
思路：每次来比较所有链表当前第一个元素，找到最小值来连接到新链表后，接着更新该位置链表的当前值，之后不断循环比较即可。
//方式一：比较法 /** * 思路：遍历数组，每次找出最小的值连接到dummy结点上，对应的数组位置也进行改变。 * 学习：https://www.bilibili.com/video/BV1QK4y1N7ww?spm_id_from=333.337.search-card.all.click * * 时间复杂度0(n*m)，空间复杂度O(1) * 执行用时：233 ms, 在所有 Java 提交中击败了5.25%的用户 * 内存消耗：43.5 MB, 在所有 Java 提交中击败了18.49%的用户 */ public ListNode mergeKLists(ListNode[] lists) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (true) { int minIndex = -1; for (int i = 0; i < lists.length; i++) { if (lists[i] == null) { continue; } if (minIndex == -1) { minIndex = i; }else{ //比较链表的结点，取到最小的结点 if (lists[i].val <= lists[minIndex].val) { minIndex = i; } } } //若是找到最小的结点位置 if (minIndex != -1) { cur.next = lists[minIndex]; cur = cur.next; lists[minIndex] = lists[minIndex].next; } //若是当前没有最小的结点位置了 if (minIndex == -1) { return dummy.next; } } }
方式二：堆排序法（对于最小值比较可使用优先队列来实现）
思路：一开始将多个数组的第一个元素全部扔到堆中(优先队列)，接着以堆当前的数量为条件不断的添加进入以及取出最小值连接到新链表上。
相较于方式一：省去了多次重复的比较，因为在方式一中每次一轮比较都是n个链表的数量元素，中间会有多次重复比较，而在这里时间效率直接提升，每次都是放在一个升序的队列里。 /** * 方式二：堆排序法 * 思路：使用优先队列，首先将所有链表的首元素添加到队列中，接着以队列的元素数量作为条件来进行不断的添加与取出最小的值连接到最新的链表，最终就可以得到一个升序的链表。 * * 执行用时：4 ms, 在所有 Java 提交中击败了63.11%的用户 * 内存消耗：43 MB, 在所有 Java 提交中击败了80.38%的用户 */ public ListNode mergeKLists(ListNode[] lists) { //优先队列（可看做是堆） PriorityQueue<ListNode> heap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val); //将当前队列扔到堆中排序 for (ListNode list : lists) { if (list != null) { heap.offer(list); } } //定义虚拟头结点 ListNode dummy = new ListNode(-1); ListNode cur = dummy; //以堆中heap的数量作为条件 while (heap.size() > 0) { ListNode node = heap.poll();//最小的元素 cur.next = node; cur = cur.next; //向堆中添加新的元素 if (node.next != null) { heap.offer(node.next); } } return dummy.next; }
其他：
方法：①遍历所有链表存到数组中。②对数组进行快速排序。③对排序后的数组进行生成链表返回。
时间复杂度：O(n+logn.n+n)=>O(logn)
空间复杂度：O(n+n)=>O(n)，排序与创建都用到O(n)
