【数据结构与算法 | 灵神题单 | 插入链表篇】力扣2807, LCR 029, 147

1. 力扣2807：在链表中插入最大公约数

1.1 题目：

你一个链表的头 head ，每个结点包含一个整数值。

在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。

请你返回插入之后的链表。

两个数的 最大公约数 是可以被两个数字整除的最大正整数。

示例 1：

输入：head = [18,6,10,3]
输出：[18,6,6,2,10,1,3]
解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
- 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。
- 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。
- 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。
所有相邻结点之间都插入完毕，返回链表。

示例 2：

输入：head = [7]
输出：[7]
解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。
没有相邻结点，所以返回初始链表。

提示：

• 链表中结点数目在 [1, 5000] 之间。
• 1 <= Node.val <= 1000

1.2 思路

这题的难点在于如果求两个相邻节点的最大公约数。如果两个值中的最大值可以与最小值整除，那么最小值就是最大公约数，否则我们用更相减损术（夸克搜的）。

1.3 题解：

/*** 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 insertGreatestCommonDivisors(ListNode head) {if(head == null || head.next == null){return head;}ListNode dummy = new ListNode(10086, head);ListNode cur = dummy;// 用来求最大公约数while(cur.next != null && cur.next.next != null){int a = cur.next.val;int b = cur.next.next.val;int max = Integer.max(a, b);int min = Integer.min(a, b);// 如果可以整除，最小值就是最大公约数if(max % min == 0){} else {// 更相减损术int sub = max - min;while(sub != min){max = Integer.max(sub, min);min = Integer.min(sub, min);sub = max - min;}}ListNode p = new ListNode(min, cur.next.next);cur.next.next = p;// 这里是p的原因在于：我们要处理的是cur的下一个节点和下下一个节点// 而p此时位于的节点刚好在要处理的两个节点前面cur = p;}return dummy.next;}
}

2. 力扣LCR：029：循环有序列表的插入

2.1 题目：

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

示例 1：

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]

提示

• 0 <= Number of Nodes <= 5 * 10^4
• -10^6 <= Node.val <= 10^6
• -10^6 <= insertVal <= 10^6

2.2 思路：

先遍历链表找到链表中最新的最大值节点，该节点的next节点即该链表的最小值节点（可能会有很多个最小值节点，但该最小值节点是边界）。

从最小值节点开始遍历，碰到合适的位置就可以插入，然后返回head即可。如果直到遍历完链表，仍然找不到位置插入，该需要插入节点的值比整个链表的值都要大或都要小，则需要插入到最小值节点的后面，这个时候我们就可以想到找到该最小值节点的上一个节点，parent节点跟踪最小值节点min_point。然后处理parent节点和要插入节点的关系即可。

2.3 题解：

/*
// Definition for a Node.
class Node {public int val;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _next) {val = _val;next = _next;}
};
*/class Solution {public Node insert(Node head, int insertVal) {Node insert = new Node(insertVal);// 如果链表为空，需要特殊判断if(head == null){insert.next = insert;return insert;}// 遍历链表找到最小值节点// 发现最新的最大值的后面就是最小值// 因为最大值可能有很多个，我们要最新的，所以p.val >= max有等于号int max = head.val;Node max_point = head;Node p = head.next;// n表示链表的长度int n = 1;while(p != head){if(p.val >= max){max = p.val;max_point = p;}n++;p = p.next;}// max_point指向了最大值的节点Node min_point = max_point.next;Node parent = null;while(n-- > 0){// 找到合适的地方就插入if(min_point.val <= insertVal && insertVal <= min_point.next.val){insert.next = min_point.next;min_point.next = insert;return head;}parent = min_point;min_point = min_point.next;}// 还没插入成功，插到最小值后面insert.next = parent.next;parent.next = insert;return head;}
}

3. 力扣147：对链表进行插入排序

3.1 题目：

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示：

• 列表中的节点数在 [1, 5000]范围内
• -5000 <= Node.val <= 5000

3.2 思路：

由于个人实力太菜，写着一跑就超时了，无奈转换成求解数组的插入排序。

3.3 题解

/*** 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 insertionSortList(ListNode head) {// 特殊情况直接返回if(head == null || head.next == null) {return head;}ListNode node = head;int n = 0;while(node != null){n++;node = node.next;}int[] arr = new int[n];node = head;n = 0;while(node != null){arr[n++] = node.val;node = node.next;}for(int i = 1; i < arr.length; i++){int t = arr[i];int j = i - 1;while(j >= 0 && t < arr[j]){arr[j+1] = arr[j];j--;}if(j != i - 1){arr[j+1] = t;}}node = head;int k = 0;while(node != null){node.val = arr[k++];node = node.next;}return head;}
}