[小点整合]
1、题目分析
????????（1）明确题意，包括输入输出、数据范围、考察具体的知识点；
? ? ? ? （2）列出所有的解决方法；
? ? ? ? （3）评估每种方法的时间、空间复杂度；
? ? ? ? （4）实现最优的解决方案，注意代码准确度并进行相关的测试；
? ? ? ? （5）进行复盘与整理，补充不足。
2、数组：内存中连续一段的存储区域，下标从0开始，插入与删除的平均时间复杂度为O(n)，查询可以在O(1)时间完成，根据元素的下标进行访问；
? ? ? ? 链表：存储空间不连续，可以减少插入和删除操作的耗时，可以在O(1)时间内完成，但前提是花费O(n)的时间去查找该元素的位置，同时其大小不确定；形式多样。
????????两者属于“博弈、动态平衡的关系”，都有其适用的场景。
[链表相关题目]
1、反转链表一
给单链表的头节点?head?，请反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2] 输出：[2,1]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目范围是?
[0, 5000] -5000 <= Node.val <= 5000
?（1）利用外部空间：先申请一个动态扩容的数组或者容器（e.g. ArrayList）；遍历链表，将链表中的元素添加到容器中；再使用容器的反转操作、或反向遍历重新存储，即可得到结果。
Collections.reverse(arrayList);?（2）双指针迭代：可以申请两个指针，第一个指针叫 prev，最初指向 null ；第二个指针 curr 指向 head，然后不断遍历 curr。——
????????每次迭代到 curr，都将 curr 的 next 指向 prev，然后 prev 和 curr 前进一位。
????????都迭代完(curr 变成 null )，prev 就是最后一个节点了。
? ? ? ? 其中，申请一个temp变量，这个temp变量会将curr的下一个节点保存起来。
????????????????时间复杂度：O(n)，假设?n 是列表的长度，时间复杂度是?O(n)。
????????????????空间复杂度：O(1)。
（3）递归解法：其关键在于反向工作。假设列表的其余部分已经被反转，现在应该如何反转它前面的部分？
????????假设列表为：
?????????若从节点?
????????????????????????????????到?
??已经被反转，而head正处于
?，如下：
????????希望?
????????所以，
?。
????????要小心的是
的下一个必须指向
。如果忽略了这一点，链表中可能会产生循环。如果使用大小为 2 的链表测试代码，则可能会捕获此错误。
????????????????时间复杂度：O(n)，假设 n 是列表的长度，时间复杂度为 O(n)。
????????????????空间复杂度：O(n)，使用递归，将会使用隐式栈空间，深度可能会达到 n 层。reverseList: head=1 reverseList: head=2 reverseList: head=3 reverseList:head=4 reverseList:head=5 终止返回 cur = 5 4.next.next->4，即5->4 cur=5 3.next.next->3，即4->3 cur = 5 2.next.next->2，即3->2 cur = 5 1.next.next->1，即2->1 最后返回cur
/**
* 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){
return null;
}
// 声明存储空间，双指针法
ListNode curr = head;
ListNode prev = null;
while(curr != null){
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}/**
* 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;
}
// 递归求解
ListNode curr = reverseList(head.next);
// 调整方向并删除原始指向关系
head.next.next = head;
head.next = null;
return curr;
}
}?2、反转链表二：指针的指向修改
????????给单链表的头指针?head?和两个整数?left?和?right?，其中?left <= right?。请反转从位置?left?到位置?right?的链表节点，返回?反转后的链表?。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1 输出：[5]
提示：
- 链表中节点数目为?
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
（1）双指针头插法：
? ? ? ? a、定义两个指针，分别称之为 g(guard 守卫) 和 p(point)：首先根据方法的参数 m 确定 g 和 p 的位置。将 g 移动到第一个要反转的节点的前面，将 p 移动到第一个要反转的节点的位置上。以 m=2，n=4为例。
? ? ? ? b、将 p 后面的元素删除，然后添加到 g 的后面。即头插法。
????????c、根据 m 和 n 重复步骤（b）
????????d、返回 dummyHead.next
?
/**
* 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 reverseBetween(ListNode head, int left, int right) {
// 判断链表是否为空
if(head == null){
return new ListNode(0);
}
// 计算链表的长度，遍历(从头到尾打印链表，面试题06)
int linkedlistLen = 0;
ListNode temp = head;
while(temp != null){
linkedlistLen += 1;
temp = temp.next;
}
// 判定left 、 right的大小关系(扩充情况)
// 1、left right长度均在链表内但right < left
// 2、在left <= right条件下，left在链表内但right超出界限
// 3、在left <= right条件下，left已经超出链表长度
// 4、left right长度均在链表内，且left <= right
if(left < linkedlistLen && right < linkedlistLen && left > right){
int flag = left;
left = right;
right = flag;
}else if(left <= right && left < linkedlistLen && right > linkedlistLen){
right = linkedlistLen;
}else if(left <= right && left > linkedlistLen){
return head;
}else if(left <= right && left < linkedlistLen && right < linkedlistLen){
// 进行后续操作，左右边界不变
}
// 使用头插法进行反转
// 创建哑节点，dummyHead
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// 初始化双指针
ListNode guard = dummyHead;
ListNode point = dummyHead.next;
// 移动指针到相应的left位置
for(int i = 0; i < left - 1; i ++){
guard = guard.next;
point = point.next;
}
// 头插法插入节点
for(int i = 0; i < right - left; i ++){
ListNode target = point.next;
point.next = point.next.next;
target.next = guard.next;
guard.next = target;
}
// 返回头节点
return dummyHead.next;
}
}