206-反转链表

image.png
题意分析：

  • 反转单链表所有节点。

解题思路：

  1. 迭代。指针一次遍历，迭代反转节点指向。
  2. 递归。针对每个节点递归调用。

注意点：

  1. 递归。
    1. 递归体和反转逻辑的先后顺序。

代码：

  1.     /**
  2.      * 迭代思路。反转指针的指向。
  3.      * @param head
  4.      * @return
  5.      */
  6.     public ListNode reverseList(ListNode head) {
  7.         ListNode pre = null;
  8.         ListNode curr = head;
  9.         while (curr != null) {
  10.             ListNode next = curr.next;
  11.             curr.next = pre;
  12.             pre = curr;
  13.             curr = next;
  14.         }
  15.         return pre;
  16.     }
  18.     /**
  19.      * 递归思路。
  20.      *  1、找到递归体
  21.      *  2、确定退出条件
  22.      * @param head
  23.      * @return
  24.      */
  25.     public ListNode reverseList2(ListNode head) {
  26.         if (head == null || head.next == null) {
  27.             return head;
  28.         }
  29.         ListNode newHead = reverseList(head.next);
  30.         head.next.next = head;
  31.         head.next = null;
  32.         return newHead;
  33.     }

92-反转链表II

image.png
题意分析：

  • 反转单链表中的一段节点。

解题思路：

  • 插入排序思想。找到要反转链表节点区域的前驱节点，然后通过插入排序反转。

代码：

  1.     public ListNode reverseBetween(ListNode head, int left, int right) {
  3.         // 增加哑节点
  4.         ListNode dummy = new ListNode();
  5.         dummy.next = head;
  7.         // 找到 left 处对应的节点，然后从这里开始插入排序逻辑反转
  8.         ListNode curr = dummy;
  9.         ListNode pre = null;
  10.         int a = left;
  11.         while (curr != null && a > 0) {
  12.             pre = curr;
  13.             curr = curr.next;
  14.             a--;
  15.         }
  17.         System.out.println(pre.val + ": " + curr.val);
  19.         ListNode next;
  20.         // 遍历要插入排序的次数，即要执行插入操作的节点个数
  21.         for (int i = 0; i < right - left; i++) {
  22.             // System.out.println("i=" + i);
  23.             if (curr.next != null) {
  24.                 next = curr.next;
  25.                 curr.next = next.next;
  26.                 next.next = pre.next;
  27.                 pre.next = next;
  28.             }
  29.         }
  30.         return dummy.next;
  31.     }

141-环形链表

image.png
题意分析：

  • 判断单链表中是否存在环。

解题思路：

  • 快慢指针。

注意点：

  • 特殊情况处理。比如空链表或者链表只有一个节点。
  • while条件的判断。
  • fast 指针走两次时第一次为 null 的处理。

代码：

  1.     public boolean hasCycle(ListNode head) {
  2.         if (head == null || head.next == null) {
  3.             return false;
  4.         }
  5.         ListNode slow = head, fast = head.next;
  7.         // 快慢指针扫描
  8.         while (fast != null) {
  9.             if (slow == fast) return true;
  10.             slow = slow.next;
  11.             // fast 走两次时容易空指针
  12.             if (fast.next == null) return false;
  13.             fast = fast.next.next;
  14.         }
  15.         return false;
  16.     }

142-环形链表II

image.png
题意分析：

  • 判断单链表是否存在环，找到环的入口

解题思路：

  • 快慢指针。先找到快慢指针找到相遇点，然后分析相遇点到入口与head节点到入口的距离同时走向。（注意：fast 指针走的距离永远是 slow 指针的2倍）

注意点：

  • 找到相遇点时，如果链表没有环，fast 指针为空，此时要先判断。

代码：

  1.     public ListNode detectCycle(ListNode head) {
  2.         if (head == null || head.next == null) {
  3.             return null;
  4.         }
  5.         // 快慢指针
  6.         ListNode slow = head, fast = head.next;
  8.         // 快慢指针扫描，找到相遇点
  9.         while (fast != null) {
  10.             //  存在环
  11.             if (slow == fast) break;
  12.             slow = slow.next;
  13.             // fast 走两次时容易空指针
  14.             if (fast.next == null) return null;
  15.             fast = fast.next.next;
  16.         }
  18.         // System.out.println(slow.val + ": " + fast.val);
  20.         // 找到环的入口 slow和fast相遇。fast走的距离始终等于slow的2倍： L(fast) = 2 L(slow)
  21.         // [3,2,0,4,5]-(-1)，该demo没有环fast为空
  22.         if (fast == null) return null;
  23.         fast = fast.next;
  24.         ListNode p = head;
  25.         while (p != fast) {
  26.             p = p.next;
  27.             fast = fast.next;
  28.         }
  29.         // 返回 fast 或者 p
  30.         return fast;
  31.     }

86-分隔链表

image.png
题意解析：

  • 将链表节点小于某个节点值的节点移动到该节点前面，并且整体节点顺序不变。

解题思路：

  1. 插入排序思想。由于要保证每个节点的初始相对位置，很容易想到插入排序，而插入排序思想的核心，无非就是要记录前面所有有序节点的最后一个节点，方便插入新数据。
    1. 时间复杂度：O(n)
    2. 空间复杂度：O(1)
  2. 合并两个链表。可以考虑将小于和大于等于x的节点单独维护一个链表，记录两个链表的头尾节点，然后合并。
    1. 时间复杂度：O(n)
    2. 空间复杂度：O(n)

注意点：

  1. 插入排序思想。
    1. 扫描时要注意更新 curr 当前节点的前驱节点 pre 更新，会出现 curr 更新到下一个节点，但 pre 节点不变，这种情况要单独处理。

代码：

  1.     /**
  2.      * 新构建两个链表，一个存储小于 x 的节点，一个存储大于 x 的节点
  3.      * @param head
  4.      * @param x
  5.      * @return
  6.      */
  7.     public ListNode partition(ListNode head, int x) {
  8.         ListNode small = new ListNode(Integer.MIN_VALUE);
  9.         ListNode smallHead = small;
  10.         ListNode large = new ListNode(Integer.MIN_VALUE);
  11.         ListNode largeHead = large;
  12.         while (head != null) {
  13.             if (head.val < x) {
  14.                 small.next = head;
  15.                 small = small.next;
  16.             } else {
  17.                 large.next = head;
  18.                 large = large.next;
  19.             }
  20.             head = head.next;
  21.         }
  22.         large.next = null;
  23.         small.next = largeHead.next;
  24.         return smallHead.next;
  25.     }
  27.     /**
  28.      * 解题思路：插入排序保证有序。
  29.      * @param head
  30.      * @param x
  31.      * @return
  32.      */
  33.     public ListNode partition2(ListNode head, int x) {
  34.         // 创建哑节点
  35.         ListNode dummy = new ListNode(Integer.MIN_VALUE, head);
  36.         // small 记录前面小于 x 的最新节点，pre 为扫描指针 curr 的前驱指针
  37.         ListNode small = dummy, pre = dummy, curr = head;
  38.         while (curr != null) {
  39.             if (curr.val < x) {
  40.                 ListNode newcurr = curr.next;
  41.                 pre.next = curr.next;
  42.                 curr.next = small.next;
  43.                 small.next = curr;
  45.                 // curr的pre节点更新需要特殊处理，比如 curr 节点原地更新，pre = curr，否则 pre 就不需要更新
  46.                 if (pre.next == curr) {
  47.                     pre = curr;
  48.                 }
  49.                 small = curr;
  50.                 curr = newcurr;
  51.             } else {
  52.                 pre = curr;
  53.                 curr = curr.next;
  54.             }
  55.         }
  56.         return dummy.next;
  57.     }

1171-从链表中删去总和值为零的连续节点(*)

image.png
题意分析：

  • 链表中连续节点（两个或者多个）如果和为零则删除，如果删除一次后还存在和为零的连续节点还需要继续删除。

解题思路：

  1. 哈希表记录（思路笔记特殊）。
    1. 时间复杂度：O(n)
    2. 空间复杂度：O(n)
  2. 前缀和（待实现）。

注意点：

  1. 哈希表记录。
    1. 难点在于哈希表key覆盖时如何重构链表。

代码：

  1. public ListNode removeZeroSumSublists(ListNode head) {
  2.         ListNode dummy = new ListNode(0, head);
  4.         Map<Integer, ListNode> map = new HashMap<>();
  6.         // 第一次扫描，建立 当前节点和与当前节点 哈希表，若哈希表 节点和 相同则覆盖
  7.         int sum = 0;
  8.         for (ListNode curr = dummy; curr != null; curr = curr.next) {
  9.             sum += curr.val;
  10.             map.put(sum, curr);
  11.         }
  13.         // 根据第一次扫描的哈希表，如果哈希表的key更新过，则说明区间数据需要删除
  14.         sum = 0;
  15.         for (ListNode curr = dummy; curr != null; curr = curr.next) {
  16.             sum += curr.val;
  17.             curr.next = map.get(sum).next;
  18.         }
  20.         return dummy.next;
  21.     }

160-相交链表

image.png
题意分析：

  • 两个链表若相交，返回相交点，否则返回 null。

解题思路：

  1. 哈希集合。遍历 A 遍历并记录链表节点，然后遍历 B 节点，第一次出现对象值一样的节点则是相交节点。
    1. 时间复杂度：O(m+n)。
    2. 空间复杂度：O(m)
  2. 双指针。A 指针走完 A 链表所有节点和 B 链表相交前的节点距离，B 指针走完 B 链表所有节点和 A 链表相交前的节点距离，两个距离是相等的，也是交叉点位置。
    1. 时间复杂度：O(m+n)。
    2. 空间复杂度：O(1)。

注意点：

  1. 哈希集合。
    1. 本地测试不太好测试，可能在相交点之前 A 和 B 中也存在相同元素，但元素的哈希值是不同的，这一点在相交情况下也是一致的。

代码：

  1. /**
  2.      * 哈希集合（List集合）
  3.      */
  4.     public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
  5.         if (headA == null || headB == null) {
  6.             return null;
  7.         }
  8.         List<ListNode> list = new ArrayList<>();
  9.         for (ListNode p = headA; p != null; p = p.next) {
  10.             list.add(p);
  11.         }
  12.         for (ListNode q = headB; q != null; q = q.next) {
  13.             if (list.contains(q)) {
  14.                 return q;
  15.             }
  16.         }
  17.         return null;
  18.     }
  20.     /**
  21.      * 双指针。
  22.      * 当存在交叉，两个指针分别走完两个链表的距离一定是相等的。
  23.      */
  24.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  25.         ListNode pa = headA, pb = headB;
  26.         while (pa != pb) {
  27.             pa = pa != null ? pa.next : headB;
  28.             pb = pb != null ? pb.next : headA;
  29.         }
  30.         return pa;
  31.     }

147-对链表进行插入排序

image.png
题意分析：

  • 数组的插入排序。

解题思路：

  • 参考数组插入排序。

注意点：

  • 插入排序时要考虑前面节点有序时插入的位置单独处理。

代码：

  1.     public ListNode insertionSortList(ListNode head) {
  2.         if (head == null || head.next == null) {
  3.             return head;
  4.         }
  6.         // 增加哑节点，方便统一处理
  7.         ListNode dummy = new ListNode(Integer.MIN_VALUE);
  8.         dummy.next = head;
  10.         // 从第二个节点开始处理
  11.         ListNode curr = head.next;
  12.         ListNode sort_last = head;
  13.         while (curr != null) {
  14.             int curr_val = curr.val;
  16.             // 两种情况，前面节点有序，一种不修改前面排序状态，一种要修改前面排序状态
  17.             if (curr_val >= sort_last.val) {
  18.                 sort_last = sort_last.next;
  19.             } else {
  20.                 // 从第一个节点开始遍历
  21.                 ListNode p = dummy;
  22.                 // 这个位置判断 p.next.val 比较巧妙，这样找不大于 curr_val 的节点时不要单独申请空间记录其前驱节点
  23.                 while (p.next.val <= curr_val) {
  24.                     p = p.next;
  25.                 }
  26.                 sort_last.next = curr.next;
  27.                 curr.next = p.next;
  28.                 p.next = curr;
  29.             }
  30. //            Utils.printList(dummy.next);
  31.             curr = sort_last.next;
  32.         }
  33.         return dummy.next;
  34.     }

148-排序链表（归并排序）

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode sortList(ListNode head) {
  2.         if (head == null || head.next == null) {
  3.             return head;
  4.         }
  6.         // 寻找链表中节点
  7.         ListNode slow = head, fast = head;
  8.         while (fast.next != null && fast.next.next != null) {
  9.             slow = slow.next;
  10.             fast = fast.next.next;
  11.         }
  13. //        System.out.println("slow = " + slow.val);
  14.         ListNode mid = slow;
  15.         ListNode right = mid.next;
  16.         mid.next = null;
  17.         ListNode l1 = sortList(head);
  18.         ListNode l2 = sortList(right);
  20.         return merge(l1, l2);
  21.         }
  23.     /**
  24.      * 合并两个有序链表
  25.      * @param l1
  26.      * @param l2
  27.      * @return
  28.      */
  29.     public ListNode merge(ListNode l1, ListNode l2) {
  30.         ListNode head = new ListNode(Integer.MAX_VALUE);
  31.         ListNode cur = head;
  32.         ListNode p1 = l1, p2 = l2;
  33.         while (p1 != null && p2 != null) {
  34.             ListNode tmp;
  35.             if (p1.val < p2.val) {
  36.                 tmp = p1;
  37.                 p1 = p1.next;
  38.             } else {
  39.                 tmp = p2;
  40.                 p2 = p2.next;
  41.             }
  42.             cur.next = tmp;
  43.             cur = cur.next;
  44.         }
  46.         if (p1 != null) cur.next = p1;
  48.         if (p2 != null) cur.next = p2;
  50.         return head.next;
  51.     }

19-删除链表的倒数第 N 个节点

image.png
题意分析：

  • 给定链表，删除倒数的某一个节点。

解题思路：

  1. 两次扫描。第一次计算链表长度，第二次找到要删除的节点。
    1. 时间复杂度：O(2n)
    2. 空间复杂度：O(1)
  2. 双指针。快慢指针同时扫描，快指针先走 n 个节点，然后快慢指针同时走，但快指针走到尾节点时，满指针就是倒数第 n 个节点（快慢指针始终相差 n 个节点）。
    1. 时间复杂度：O(n)
    2. 空间复杂度：O(1)
  3. 辅助栈。先将链表元素都入栈，然后依次出栈元素到倒数第 n 个节点。
    1. 时间复杂度：O(n)
    2. 空间复杂度：O(n)

注意点：
代码：

  1.     /**
  2.      * 思路一：两次扫描链表，第一次获取链表长度，第二次找到要删除的节点
  3.      * @param head
  4.      * @param n
  5.      * @return
  6.      */
  7.     public ListNode removeNthFromEnd1(ListNode head, int n) {
  8.         ListNode nHead = new ListNode(-1, head);
  9.         ListNode p = nHead;
  10.         ListNode idx = nHead, idxPre = nHead;
  11.         int len = 0;
  12.         // 统计链表长度
  13.         while (p != null) {
  14.             p = p.next;
  15.             len++;
  16.         }
  17.         // 要遍历的元素位置
  18.         int k = len - n + 1;
  19.         int i = 1;
  20.         while (i++ < k) {
  21.             idxPre = idx;
  22.             idx = idx.next;
  23.         }
  24.         if (idxPre == nHead) {
  25.             idxPre.next = null;
  26.         } else {
  27.             idxPre.next = idx.next;
  28.         }
  29.         return nHead.next;
  30.     }
  32.     /**
  33.      * 思路二：利用辅助栈，出栈时找对要删除的元素
  34.      * @param head
  35.      * @param n
  36.      * @return
  37.      */
  38.     public ListNode removeNthFromEnd2(ListNode head, int n) {
  39.         ListNode nHead = new ListNode(-1, head);
  40.         Deque<ListNode> stack = new LinkedList<>();
  41.         ListNode p = nHead;
  42.         while (p != null) {
  43.             stack.push(p);
  44.             p = p.next;
  45.         }
  46.         ListNode idx = nHead;
  47.         // 退到要删除的元素为止
  48.         for (int i = 0; i < n; i++) {
  49.             idx = stack.pop();
  50.         }
  52.         ListNode idxPre = nHead;
  53.         if (stack.isEmpty()) {
  54.             idx.next = null;
  55.         } else {
  56.             idxPre = stack.pop();
  57.             idxPre.next = idx.next;
  58.         }
  59.         return nHead.next;
  60.     }
  62.     /**
  63.      * 思路三：利用快慢指针，两个指针始终相差n个元素，当快指针扫描到链表最后一个元素，此时慢指针所在的元素就是要删除的元素
  64.      * @param head
  65.      * @param n
  66.      * @return
  67.      */
  68.     public ListNode removeNthFromEnd3(ListNode head, int n) {
  69.         ListNode nHead = new ListNode(-1, head);
  70.         // 快慢指针
  71.         ListNode fast = nHead, slow = nHead;
  72.         // 辅助指针
  73.         ListNode p = nHead, slowPre = nHead;
  75.         // 快指针先走了n个位置
  76.         for(int i = 1; i <= n; i++){
  77.             fast = p;
  78.             p = p.next;
  79.         }
  81.         while (fast.next != null) {
  82.             fast = fast.next;
  83.             slowPre = slow;
  84.             slow = slow.next;
  85.         }
  87.         // 特殊情况，如果链表只有一个元素，slowPre 其实和 slow 指针是对等的，无法按照正常逻辑去处理
  88.         if (slowPre == slow) {
  89.             slowPre.next = null;
  90.         } else {
  91.             slowPre.next = slow.next;
  92.         }
  93.         return nHead.next;
  94.     }

61-旋转链表

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode rotateRight(ListNode head, int k) {
  2.         if (k == 0 || head == null || head.next == null) {
  3.             return head;
  4.         }
  5.         int len = 1;
  6.         ListNode p = head;
  7.         // 遍历到链表尾节点
  8.         while (p.next != null) {
  9.             len++;
  10.             p = p.next;
  11.         }
  12.         // 链表尾部和头部形成闭环
  13.         p.next = head;
  15.         // 记录从尾部指针移动多少次走到新尾部节点
  16.         int mvLen = len - k % len;
  17.         while (mvLen-- > 0) {
  18.             p = p.next;
  19.         }
  20.         ListNode newHead = p.next;
  21.         p.next = null;
  22.         return newHead;
  23.     }

去重问题

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

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode deleteDuplicates(ListNode head) {
  2.         if (head == null) {
  3.             return head;
  4.         }
  5.         ListNode dummy = new ListNode(-101, head);
  6.         ListNode cur = dummy;
  7.         while (cur.next != null) {
  8.             if (cur.val == cur.next.val) {
  9.                 cur.next = cur.next.next;
  10.             } else {
  11.                 cur = cur.next;
  12.             }
  13.         }
  14.         return dummy.next;
  15.     }


82-删除排序链表中的重复元素II

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode deleteDuplicates(ListNode head) {
  2.         if (head == null) {
  3.             return head;
  4.         }
  5.         ListNode dummy = new ListNode(-101, head);
  6.         ListNode cur = dummy;
  7.         while (cur.next != null && cur.next.next != null) {
  8.             if (cur.next.val == cur.next.next.val) {
  9.                 // 开始遍历重复元素个数，并删除
  10.                 int tmp = cur.next.val;
  11.                 while (cur.next != null && cur.next.val == tmp) {
  12.                     cur.next = cur.next.next;
  13.                 }
  14.             } else {
  15.                 cur = cur.next;
  16.             }
  17.         }
  18.         return dummy.next;
  19.     }


未分类

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

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode swapPairs(ListNode head) {
  2.         ListNode dummyHead = new ListNode(0);
  3.         dummyHead.next = head;
  4.         ListNode temp = dummyHead;
  5.         while (temp.next != null && temp.next.next != null) {
  6.             ListNode node1 = temp.next;
  7.             ListNode node2 = temp.next.next;
  8.             temp.next = node2;
  9.             node1.next = node2.next;
  10.             node2.next = node1;
  11.             temp = node1;
  12.         }
  13.         return dummyHead.next;
  14.     }


21-合并两个有序链表

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  2.         ListNode head = new ListNode(Integer.MAX_VALUE);
  3.         ListNode cur = head;
  4.         ListNode p1 = l1, p2 = l2;
  5.         while (p1 != null && p2 != null) {
  6.             ListNode tmp;
  7.             if (p1.val < p2.val) {
  8.                  tmp = p1;
  9.                 p1 = p1.next;
  10.             } else {
  11.                 tmp = p2;
  12.                 p2 = p2.next;
  13.             }
  14.             cur.next = tmp;
  15.             cur = cur.next;
  16.         }
  18.         if (p1 != null) cur.next = p1;
  20.         if (p2 != null) cur.next = p2;
  22.         return head.next;
  23.     }

23-合并K个升序链表

image.png
题意分析：

  • 合并 K 个升序链表。

解题思路：

  • 优先级队列（最小堆）。队列先添加所有链表的 head 节点（每次添加都是最小节点），然后取队列元素并添加其 next 元素到队列中。
    • 时间复杂度：优先级队列中最多有 k 个元素，单个节点插入和删除的时间复杂度为 O(logk），总共有 kn 个节点，每个节点都要被插入和删除一次，故总的时间复杂度为 O(kn * logk)。
    • 空间复杂度：优先级队列的大小 O(k)。

注意点：

  • 优先级队列添加对象时需要实现 Compartor 对象。
  • TreeSet 可以实现按顺序添加元素和取最小元素，但不能添加重复元素。

扩展：
代码：

  1.     /**
  2.  * 合并 k 个升序链表
  3.  *
  4.  * 思路：
  5.  *  1、添加所有链表的 head 节点
  6.  *  2、循环从中拿到最小节点，然后添加其 next 元素
  7.  */
  8.     public ListNode mergeKLists(ListNode[] lists) {
  9.         // 构建优先级队列（最小堆），队列元素添加排序规则
  10.         Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
  11.             // 升序排序器，默认就是最小堆
  12.             @Override
  13.             public int compare(ListNode o1, ListNode o2) {
  14.                 return o1.val - o2.val;
  15.             }
  16.         });
  17.         // 添加所有链表的 head 节点
  18.         for (ListNode list : lists) {
  19.             if (list != null)
  20.             queue.offer(list);
  21.         }
  22.         // 增加哨兵节点
  23.         ListNode newHead = new ListNode(-1);
  24.         ListNode currTail = newHead;
  26.         // 循环出队列，并添加新元素到队列
  27.         while (!queue.isEmpty()) {
  28.             ListNode node = queue.poll();
  29.             if (node.next != null) {
  30.                 queue.offer(node.next);
  31.             }
  32.             currTail.next = node;
  33.             currTail = node;
  34.             node.next = null;
  35.         }
  36.         return newHead.next != null ? newHead.next : null;
  37.     }

1669-合并两个链表

image.png
题意分析：
解题思路：
注意点：
代码：

  1.     public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
  3.         // 获取链表 1 的前半部分结束节点 和 后半部分的开始节点
  4.         ListNode head1 = list1, tail1 = list1;
  5.         ListNode curr1 = list1;
  6.         while (curr1 != null && b > 0) {
  7.           if (a > 0) {
  8.               head1 = curr1;
  9.               a--;
  10.           }
  11.             curr1 = curr1.next;
  12.             b--;
  13.         }
  14.         tail1 = curr1.next;
  16.         System.out.println("head1 = " + head1.val + "; tail1 = " + tail1.val);
  18.         // 获取链表 2 的头节点和尾节点
  19.         ListNode head2 = list2;
  20.         while (list2.next != null) {
  21.             list2 = list2.next;
  22.         }
  23.         ListNode tail2 = list2;
  25.         System.out.println("head2 = " + head2.val + "; tail2 = " + tail2.val);
  27.         // 连接链表
  28.         head1.next = head2;
  29.         tail2.next = tail1;
  30.         return list1;
  31.     }

模版

题意分析：
解题思路：
注意点：
扩展：
代码：