24.两两交换链表中的节点
题目描述：
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
示例 1：
输入：head = [1,2,3,4]
输出：[2,1,4,3]
示例 2：
输入：head = []
输出：[]
示例 3：
输入：head = [1]
输出：[1]
解题思路
举例：[1,2,3,4] 利用虚拟头节点 -> [0,1,2,3,4]
image.png
var swapPairs = function(head) {
let dymmic = new ListNode(0, head);
let cur = dymmic;
while(cur && cur.next && cur.next.next) {
let pre = cur.next; // pre = [1,2,3,4]
cur.next = cur.next.next; // cur = [0,2,3,4]
let next = cur.next.next; // next = [3,4]
cur.next.next = pre; // cur = [0,2,1,2,3,4]
pre.next = next; // pre = [1,3,4]
cur = pre; // cur = [0,2,1,3,4]
}
return dymmic.next;
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
19.删除链表的倒数第 N 个结点
题目描述：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
解题思路
- 利用快慢指针
- 快指针：先一步移动n个步数
- 慢指针：等快指针到达n个步数后，快慢指针一同移动，直到快指针的next为null，此时慢指针的指向即为倒数第N的节点
var removeNthFromEnd = function(head, n) {
let dymmic = new ListNode(0, head);
let fast = dymmic;
let slow = dymmic;
while(n--) {
fast = fast.next
}
while(fast.next) {
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return dymmic.next;
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
面试题 02.07. 链表相交
题目描述：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点c1开始相交：
image.png
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
示例1：
image.png
输入：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：
image.png
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：
image.png
输入：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 。
解题思路
- 首先计算 A,B 两个链表分别的长度
- 计算差值diffDep，让长链表首先移动diffDep个步数
- 再让A，B两个链表同时移动，直到找到相同的头节点，返回即可
- 否则返回null
注意
1 判断头节点是否相等：比较的是节点指向而不是节点值
var getIntersectionNode = function(headA, headB) {
let A = headA;
let Alen = 0
let B = headB;
let Blen = 0;
while(A) {
A = A.next;
Alen++
}
while(B) {
B = B.next;
Blen++
}
let diffDep = Math.abs(Alen - Blen)
while (diffDep--) {
if (Alen > Blen) {
headA = headA.next
} else {
headB = headB.next
}
}
while(headA) {
if (headA === headB) {
return headA
} else {
headA = headA.next
headB = headB.next
}
}
return null
};
- 时间复杂度：O(n+m)
- 空间复杂度：O(1)
142. 环形链表 II
题目描述：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
示例 1：
image.png
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
image.png
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
image.png
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
解题思路
- 判断链表是否为环行链表
- 如果为环形链表，如何找到环形入口
如何判断链表是否为环形
使用快慢指针法，分别设置fast和slow，从头节点出发，fast一次移动2个节点，slow一次移动1个节点，如果途中相遇，则为环形链表。
如何找到环形入口
从头节点出发1个指针，从相遇节点出发1个指针，这两个指针每次同时只移动1个节点，当这两个指针相遇的时候就是环形入口的节点。
var detectCycle = function(head) {
if (!head || !head.next) {
return null
}
let fast = head.next.next;
let slow = head.next;
while(fast && fast.next && fast !== slow) {
slow = slow.next
fast = fast.next.next
}
if (!fast || !fast.next) {
return null
}
slow = head;
while (slow !== fast) {
slow = slow.next
fast = fast.next
}
return slow;
};
环形链表推理请参考：代码随想录
另外友友们，有没有好用的画图软件推荐呀
网友评论