双指针
# 双指针
# lc160. 求相交链表的第一个相交节点/相交链表简单hot
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例 1：
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
2
3
4
5
示例 2：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
2
3
4
5
双指针 来清除高度差
我们知道这两个链表有可能是不一样的长度的，我们需要清楚高度差，然后让两个链表同时运动的节点相遇然后来找到相交的点
来个图助助兴
- 首先先同步遍历
AB链表pA和pB直到遍历完一个短链
pB先遍历完 然后pB指针指到A链表，然后进行下一次遍历，当pA遍历完pA指向B链表
- 然后一直循环直到
pB和pA指向同一个节点，即为相交的第一个节点
- 如果没有相交那就返回
null
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let pA = headA
let pB = headB
while(pA !== pB){
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return pA
};
2
3
4
5
6
7
8
9
10
11
12
13
14
时间复杂度O(n)
空间复杂度O(1)
# lc203. 移除链表元素简单
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
2
3
示例 2：
输入：head = [], val = 1
输出：[]
2
3
示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
2
3
var removeElements = function(head, val) {
let dummyHead = new ListNode(null)
dummyHead.next = head
let pre = dummyHead
let cur = head
while(cur) {
cur.val === val ? pre.next = cur.next : pre = cur
cur = cur.next
}
return dummyHead.next
};
2
3
4
5
6
7
8
9
10
11
12
时间复杂度:O(n)
空间复杂度:O(1)
# lc83. 删除排序链表的重复元素简单hot
题目描述
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,1,2]
输出：[1,2]
2
3
示例 2：
输入：head = [1,1,2,3,3]
输出：[1,2,3]
2
3
思路同移除链表元素一样
var deleteDuplicates = function(head) {
let duummyHead = new ListNode(null)
duummyHead.next = head
let pre = duummyHead
let cur = head
while(cur) {
cur.val === pre.val ? pre.next = cur.next : pre = cur
cur = cur.next
}
return duummyHead.next
};
2
3
4
5
6
7
8
9
10
11
12
时间复杂度:O(n)
空间复杂度:O(1)
# lc82. 删除排序链表的重复元素 II中等hot
题目描述
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
2
3
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
2
3
var deleteDuplicates = function(head) {
// 处理链表只有0或1个节点的情况
if(!head||!head.next){
return head
}
// 设置虚拟头节点
let dummy = new ListNode(null)
dummy.next = head
// 设置当前节点
let cur = dummy
while (cur.next && cur.next.next){
if(cur.next.val === cur.next.next.val){
// 保存重复节点的值
let val =cur.next.val
// 反复判断是否还有相等的节点
while(cur.next && cur.next.val === val){
cur.next = cur.next.next
}
}else{
cur = cur.next
}
}
// 返回最终结果，也就是链表的起始的节点
return dummy.next
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
时间复杂度:O(n)
空间复杂度:O(1)
# lc147. 对链表进行插入排序中等
题目描述
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
2
3
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
2
3
思路
就是设置一个last和first节点，first节点都在last节点之后，首先先让first节点和last节点进行比较，如果大于last节点，那么就顺序不改变，如果小于last节点的话，就从头开始遍历链表进行插入
/**
* @param {ListNode} head
* @return {ListNode}
*/
var insertionSortList = function(head) {
if(!head) return head
let last = head
let first = head.next
let dummyHead = new ListNode(null)
dummyHead.next = head
while(first) {
if(last.val <= first.val) {
last = last.next
} else {
let cur = dummyHead
while(cur.next.val <= first.val) {
cur = cur.next
}
last.next = first.next
first.next = cur.next
cur.next = first
}
first = last.next
}
return dummyHead.next
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
- 时间复杂度：
O(n)，对于链表而言，插入元素时只要更新相邻节点的指针即可，因此插入操作的时间复杂度是O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是O(n)，因此链表插入排序的总时间复杂度仍然是O(n)，其中n是链表的长度。 - 空间复杂度：
O(1)，需要额外的常数大小的辅助空间。
# lc328. 奇偶链表中等
题目描述
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
2
3
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
2
3
var oddEvenList = function(head) {
if(head === null || head.next === null || head.next.next === null){
return head
}
let a = head // 存放奇数节点
let b = head.next // 存放偶数节点
const node = head.next // 记录b链表的头节点
while(b && b.next){
a.next = b.next
a = a.next
b.next = a.next
b = b.next
}
a.next = node
return head
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
时间复杂度:O(n)
空间复杂度:O(1)