代码随想录算法训练营第四天 | leetcode：两两交换链表中的节点,删除链表的倒数第N个节点,环形链表II,面试题 02.07
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
Problem: 24. 两两交换链表中的节点)
需要注意的问题
- 指针起始位置在哪？如何移动？
- 当两两交换时，交换顺序是怎样的？
- 注意交换过程中，当前能获取到的next是否符合预期？不符合应该如何处理？
解题方法
- 设置虚拟头结点，指针初始位置指向虚拟头结点，当操作完毕后，指针指向需要交换节点的前一个位置，即往后移动两位。
- 两两交换过程中，遵循213原则。即：先处理虚拟头结点指向第二节点，第二节点指向第一节点，第一节点指向第三节点。
- 当改变链表指向，导致通过链表next方式获取不到预期值时，可以使用临时变量存储值后，再处理节点指向。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
function swapPairs($head) {
$dummyHead = new ListNode();
$dummyHead->next = $head;
$cur = $dummyHead;
//需要判断$cur->next->next != NULL，不然下面获取tepm3容易发生空指针异常。
while($cur->next != NULL && $cur->next->next != NULL){
//存储第一个节点
$temp1 = $cur->next;
//存储第三个节点
$temp3 = $cur->next->next->next;
//当前指针->next先指向第二个节点
$cur->next = $cur->next->next;
//当前指针->next—>next指向原先第一个节点，即第一，第二节点交完完成
$cur->next->next = $temp1;
//交换完的第二个指针 指向 当前指针的第三个节点
$temp1->next = $temp3;
//指针后移两位
$cur = $cur->next->next;
}
return $dummyHead->next;
}Problem: 19. 删除链表的倒数第 N 个结点
需要注意的问题
删除节点时，指针应该指向哪里？如何移动到目标位置？
解题方法
设置虚拟头结点，使用双指针方式，快慢指针初始位置指向虚拟头结点。慢指针是操作删除元素的标识。快指针先移动N(倒数第N个节点)+1，然后快慢指针再同时移动，直到快指针指向null。此处为啥是N+1,是因为当删除节点时，慢指针需要指向目标节点的前一位。
图示：假设N=2;
- 快指针先移动N+1。
- 快慢指针同时移动，直到快指针等于null。
- 最终移动完毕指针指向。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
function removeNthFromEnd($head, $n) {
$dummyhead = new ListNode();
$dummyhead-> next = $head;
$fast = $dummyhead;
$slow = $dummyhead;
$index = $n+1; //慢指针需要指向删除节点的前一位，所以快指针需要多走一位。
//移动快指针先走的位移
while($index > 0){
$fast = $fast->next;
$index--;
}
//快慢指针一起移动
while($fast != null){
$fast = $fast->next;
$slow = $slow->next;
}
//节点删除操作
$slow->next = $slow->next->next;
return $dummyhead->next;
}Problem: 142. 环形链表 II
解题方法
找环题解：
slow慢指针：每次走一格；
fast快指针：每次走两格；
如果相遇，则链表存在环。
找环入口题解：
1. 设置参数
起始点到环形入口距离为x,
环形入口到快慢指针相遇距离为y,
相遇点再到环形入口距离为z,
slow慢指针：每次走一格；
fast快指针：每次走两格；
相遇时走的距离
慢指针 slow = x + y;
快指针 fast = x + y + n(y + z);//n为快指针追慢指针所绕的圈数
2. 因为快指针比慢指针快两倍，建立数学公式。
2（x + y） = x + y + n(y + z)
左移x+y,得：x + y = n(y + z)
右移y,得：x = n(y + z) - y
提取公因数，得：x = (n - 1)(y + z) + (y + z) - y
消除y,得：x = (n - 1)(y + z) + z
3. 结论
即：n=1时，x = y;
相遇时，设置起始位置指针 与 相遇时指针 同时以1格的速度前进 相遇的点即是环形入口复杂度
时间复杂度:
O(n)
空间复杂度:
O(1)
function detectCycle($head) {
$fast = $head;
$slow = $head;
while($fast!=null && $fast->next != null){
//快指针走2格
$fast = $fast->next->next;
//慢指针走1格
$slow = $slow->next;
//一定要全等，否则报错：Line 54: PHP Fatal error: Nesting level too deep - recursive dependency?
if($fast === $slow){
//相遇时定义一个起始点与快慢指针相遇点
$meet = $fast;//相遇点
$start = $head;//起始点
while($start != $meet){
$start = $start->next;
$meet = $meet->next;
}
return $start;
}
}
return null;
}Problem: 面试题 02.07. 链表相交
需要注意的问题
- 虽然题目给出了skipA = 2, skipB = 3。但实际写题解的地方没有传参。
- Intersected at ‘8’ 的意思是输出8所在的指针位置。交点不是数值相等，而是指针相等。
- 函数返回结果后，链表必须 保持其原始结构 。
解题方法1
分别计算链表长度，计算两个链表的长度差diffNum。使长链表指针先移动diffNum。然后两个链表指针同时移动。并且判断两个链表指针是否相等，相等的话则返回下标。
图示：
解题方法2
使用集合，先使用集合A存储链表A的所有指针。再循环链表B，其中判断集合A中是否存在链表B的指针元素。
复杂度
时间复杂度:
O(n + m) ：m为相交点前的距离
空间复杂度:
O(1)
！！！！本题leetcode无PHP解答语言，以下是JavaScript语言解法！！！！
解题方法1 Code
var getIntersectionNode = function(headA, headB) {
var aCur = headA;
var bCur = headB;
var aLen = 0;
var bLen = 0;
while(aCur){
aCur = aCur.next;
aLen++;
}
while(bCur){
bCur = bCur.next;
bLen++;
}
var aCur = headA;
var bCur = headB;
if(aLen > bLen){
var diffNum = aLen-bLen;
while(diffNum){
aCur = aCur.next;
diffNum--;
}
}
if(aLen < bLen){
var diffNum = bLen-aLen;
while(diffNum){
bCur = bCur.next;
diffNum--;
}
}
while(aCur){
if(aCur == bCur){
return aCur;
}
aCur = aCur.next;
bCur = bCur.next;
}
return null;
};解题方法2 Code
var getIntersectionNode = function(headA, headB) {
//集合求解
var A = new Set();
var aCur = headA;
var bCur = headB;
while(aCur){
A.add(aCur);
aCur = aCur.next;
}
while(bCur){
if(A.has(bCur)){
return bCur;
}
bCur = bCur.next;
}
return null
};本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号