- 1嵌入式裸机编程中使用malloc、free会怎样？
- 2AI人工智能深度学习算法：在电力预测中的应用_生成ai 电力预测
- 3Hyper-V虚拟机CentOS7固定IP地址_hyper-v centos7 固定ip设置
- 4软考高级-信息系统管理师之安全管理（最新版）_信息管理系统工程师 安全管理
- 5sklearn加载查看数据集_from sklearn import datasets
- 6springMVC拦截器_拦截器只能拦截controller
- 7易点天下基于 StarRocks 全面构建实时离线一体的湖仓方案_应用层 ads 跨层访问(穿透)
- 8强烈推荐一个Python库！制作Web Gui也太简单了！_python webgui
- 9YOLOv10改进 | 主干篇 | YOLOv10引入CVPR2023 顶会论文BiFormer用于主干修改
- 10C++第三十二弹---从概念到实践：全面解析C++多态性
双指针解决链表相关问题_链表双指针和尾指针问题
赞
踩
双指针解决链表问题
判断链表是否有环
链表有环：指的是从链表中的头节点开始，不断地连续访问next指针，可以访问到某个节点多次。
思路：
若链表中无环，那么链表的最后一个节点的next指针一定是指向NULL指针，否则链表中存在环。需要注意的是，因为链表只有一个next指针指向后面的节点，所以如果某个节点的next指针指向了前面的某个节点，那么该节点就是实际意义上的最后一个节点，因为后面的节点已经没有进行连接，无法访问到，与不存在等价。
我们很容易想到通过来判断链表的最后一个节点的next指针来判断链表中是否存在环，但是当链表中存在环的时候，当我们遍历到链表的最后一个节点的时候，不会停止循环，而是会去遍历前面的某个节点，这样就导致进入死循环，无法对问题进行求解。如果我们知道链表的长度，那我们也可以通过记录遍历的次数来找到链表的最后一个节点，从而来进行判断，但是链表的长度往往是不可知的，所以这种方法理论可行，实际不可行。
我们可以使用哈希表的思想，来存储每一个节点，如果某个节点已经存在哈希表中后还再次访问到，那就证明链表中存在环。这样子的空间复杂度是比较高的，假设链表的长度为N，那么这种方法的空间复杂度就是O(N)，时间复杂度是O(N)。
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set<ListNode*> seen;
while (head != nullptr) {
if (seen.count(head)) {
return true;
}
seen.insert(head);
head = head->next;
}
return false;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
解决这类问题，我们使用双指针的思想，也可以叫做快慢指针，将空间复杂度降低到O(1)，时间复杂度是O(N)。
我们使用两个指针，一个指针一次走两步，名为fast指针，一个指针一次只走一步，名为slow指针，刚开始都指向链表的第一个节点。
-
当链表中没有环的时候：
- 链表节点个数为2n+1：此时由于fast指针一次走两步，那么n步之后，fast节点指向第2n+1个节点，slow节点指向第n+1个节点，此时fast节点的next的指针为NULL指针，退出循环，并且链表中没有环。
- 链表节点个数为2n：走n步之后，fast指针指向的是第 1+2n节点，也就是链表的最后一个节点的next指针指向的NULL节点，slow节点指向第n+1个节点，此时fast指针是**NULL指针，退出循环，并且链表中没有环。
- 其实我们明白，fast节点走的快，对其进行赋值的时候，也就是fast = fast->next->next，当链表中不存在环的时候，最后一个节点的next指针是NULL，所以退出循环的条件就是fast == NULL || fast -> next == NULL，这与上面讨论的两种情况一致。
-
当链表中有环的时候：
此时不管是那种情况，一定会在走了某步之后，fast指针与slow指针都会进入环中，此时就变成了一个类似于操场上跑步的追击 相遇问题，fast指针每次比slow指针多走一步，那么一定会在某一步之后，两个指针指向的节点相同，此时就可以跳出循环，证 明链表中存在环，如果我们想知道环的长度，那么就可以继续重复上述过程，等到fast指针再次与slow指针相遇的时候，fast指 针正好比slow指针多走了一个环的长度，所以环的长度就是从第一次相遇到第二次相遇所走的步数。
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head,*slow = head;
while(fast && fast->next){
slow = slow -> next;
fast = fast -> next -> next;
if(slow == fast){
return true;
}
}
return false;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
这就是快慢指针的思想，当然，fast指针可以走的更快哦！！！可是循环的条件又应当怎么更改呢？？？走的更快效率是更高呢还是更低呢？剩下的事情交给聪明的你哦！
找到链表中环的起点
当判断出来链表中存在环的时候，我们应当如何找到链表中环的起点就是一个新的问题。
思路
- 哈希表的思想，将链表的每一个节点存储到哈希表中，后面遇到的第一个已经在哈希表中存储的节点就是环的入口。
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode *> visited;
while (head != nullptr) {
if (visited.count(head)) {
return head;
}
visited.insert(head);
head = head->next;
}
return nullptr;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
2.快慢指针：fast指针一次走两步，low指针一次走一步，链表中若存在环的时候，当fast指针与low指针相遇的时候，此时将一个新指针指向链表头部，该指针每一次走一步，那么该指针与low指针相遇的节点就是链表中环的起点。
证明：
我们首先证明当慢指针slow进入环之后，第一圈走不完，就一定会和快指针fast相遇。
- 快指针一定先进入环。
- 慢指针进入环的时候，快指针此时在环中的某个位置。也可能此时相遇。
- 假设快慢指针的距离为x，若在第二步相遇，则 x = 0。
- 设环的周长为 n,那么当快指针位于慢指针后面的时候，快指针需要追赶 x；当快指针位于慢指针前面的时候，需要追赶n-x。
- 每走一步，快指针与慢指针的距离就会减少1。
- 所以当快慢指针相遇的时候，慢指针一共走了x步或者n-x步，因为 0 ≤ x ≤ ( n − 1 ) 0 \le x \le (n - 1) 0≤x≤(n−1), 1 ≤ ( n − x ) ≤ n 1 \le (n-x) \le n 1≤(n−x)≤n
- 所以慢指针进入之后，一圈走不完就会与快指针相遇
在证明等量关系，假设链表中环外的长度为a，slow指针进入环中之后，走了b距离之后与fast指针相遇，此时fast指针已经走完了环的n圈，因此fast指针走过的总距离为（ b + c 为环的长度，上面已经证明了慢指针走不了一圈，b相当于慢指针进入环入口之后走的距离）：
a + n ( b + c ) + b = a + ( n + 1 ) b + n c a + n (b + c) + b = a + (n + 1) b + nc a+n(b+c)+b=a+(n+1)b+nc
因为任意时刻，fast指针走过的距离都为slow指针的二倍，slow指针走的距离为a + b,因此有：
a + ( n + 1 ) b + n c = 2 ( a + b ) a + (n + 1) b + nc = 2 (a + b) a+(n+1)b+nc=2(a+b)
a = c + ( n − 1 ) ( b + c ) a = c + (n - 1)(b + c) a=c+(n−1)(b+c)
a − c = ( n − 1 ) ( b + c ) a - c = (n - 1)(b + c) a−c=(n−1)(b+c)
所以链表中环外的长度刚好等于相遇点到入环点的距离加上n-1倍的环的长度。
slow指针再走c步之后会回到环的入口点，同时让链表的head指针也走c步，根据上面的等式
a
−
c
=
(
n
−
1
)
(
b
+
c
)
a - c = (n - 1)(b + c)
a−c=(n−1)(b+c)
可以得到head到入口的距离必然是环长的整数倍，因此两者会在入口点相遇。
class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head, *fast = head; while (fast != nullptr) { slow = slow->next; if (fast->next == nullptr) { return nullptr; } fast = fast->next->next; if (fast == slow) { ListNode *ptr = head; while (ptr != slow) { ptr = ptr->next; slow = slow->next; } return ptr; } } return nullptr; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
相交链表
判断两个链表是否相交
160. Intersection of Two Linked Lists
思路：
最简单的想法就是进行两次循环，假设链表A的长度为m,链表B的长度为n，那么我们将两个链表的每一个节点进行对比，判断其中是否存在相等，借此来判断两个链表中是否存在相交。这样做的时间复杂度为 O ( m × n ) O(m \times n) O(m×n)。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *A = headA,*B = headB; while(A != NULL){ B = headB; while(B != NULL){ if(A == B){//比较的是指针指向的地址，也就是指向得到节点 return A; } B = B->next; } A = A->next; } return NULL; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
为了降低时间复杂度，我们考虑其他方法。如果两个链表相交，那么两个链表的最后一个节点一定是一样的，那么我们就可以通过遍历链表，来判断两个链表的最后一个节点是否相同，如果相同证明两个链表相交否则两个链表没有相交。但是我们除了需要判断两个链表是否相交外还需要找到两个链表最先相交的交点，所以这种方法不可行。
我们还可以采用哈希表的思想，将一个链表中的所有节点存储在哈希表中，然后再去遍历另一个链表中的节点，第一次出现重复的节点就是两个链表相交的交点。这样子的
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set<ListNode*> hashSet; while(headA != NULL){ hashSet.insert(headA); headA = headA->next; } while(headB != NULL){ if(hashSet.count(headB)){ return headB; } headB = headB -> next; } return NULL; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
考虑到上述哈希表的解法，与之前寻找链表中环的起点十分相似，所以我们考虑能否将这个问题转换为寻找环的起点的问题。幸运的是，我们可以把链表B连接到链表A的末尾，如果链接后的链表没有环，那就证明两个链表之间没有交点，如果有环，那么合并之后的链表中就存在环，并且环的起点就是链表的交点。当我们使用双指针的解法时，时间复杂度降低到 O ( m + n ) O(m + n ) O(m+n)，但是空间复杂度为 O ( 1 ) O(1) O(1)。但是这样子会修改链表的结构，我们在后面需要将链表的结构还原。
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *temp = headA; while(temp->next != NULL){ temp = temp->next; } temp->next = headB; ListNode *fast = headA,*slow = headA; while(fast && fast->next){ fast = fast->next->next; slow = slow->next; if(fast == slow){ ListNode *ptr = headA; while(ptr != slow){ ptr = ptr->next; slow = slow->next; } temp->next = NULL; return ptr; } } temp->next = NULL; return NULL; } };
- 1
- 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
下面来欣赏官方大大的操作：
- 初始化两个指针
pA和pB，分别指向两个链表的头节点headA、headB。 - 两个指依次遍历两个链表的每个节点，每步操作同时更新指针
pA、pB。 - 如果指针
pA不为空，则指向下一个节点；如果指针pB不为空，则指向下一个节点。 - 如果指针
pA为空，则将指针指向链表headB的头节点；如果指针pB为空，则将指针指向链表headA的头节点。 - 当指针
pA、pB指向同一个节点或者都为空的时候，返回它们指向的节点或者NULL。
证明如下：
- 两个链表相交：
假设headA和headB的长度分别是m和n，链表A不相交的有a个节点，链表B不相交的有b个节点，相交的有c个节点，那么a + c = m,b + c = m。
- 如果 a = b a = b a=b，那么两个指针同时到达链表的交点，返回结果。
- 如果
a
≠
b
a \neq b
a=b，那么
pA会遍历完链表A，pB会遍历完链表B，然后pA指向链表B的头节点，pB指向链表A的头节点，在pA移动了a + c + b、pB移动了b + c + a之后，两个指针第一次同时指向相交的交点。
-
两个链表不相交：
假设
headA和headB的长度分别是m和n。
- 如果
m
=
n
m = n
m=n，那么两个指针同时到达链表的末尾，指向
NULL指针，返回结果。 - 如果
m
≠
n
m \neq n
m=n，那么由于两个指针没有相交的交点，所以在
pA移动了m + n、pB移动了m + n之后，两个指针同时指向NULL指针，返回结果。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) {
return NULL;
}
ListNode *A = headA,*B = headB;
while(A != B){
A = (A == NULL) ? headB : A->next;
B = (B == NULL) ? headA : B->next;
}
return A;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
删除链表的倒数第N个节点
19. Remove Nth Node From End of List
思路：
我们要删除链表的倒数第N个节点，首先就需要找到链表的倒数第N个节点，然后进行删除。我们可以首先遍历链表，得到链表的长度，然后再从链表的头节点开始遍历，使用一个计数器来进行计数，就可以找到该节点。假设链表的长度为M，那么倒数第N个节点就是正数第M-N+1个节点。我们从链表头部开始，经过M-N次遍历就可以找到该节点。对于删除链表中的某个节点，我们只是需要改变要删除的节点的前面的节点的next指针，然后将其指向要删除节点后面的那个节点就可以了。
假设指针p指向了要删除的节点，指针q指向的是要删除的节点的前面一个节点，那么上述操作即为：
q -> next = p -> next;
- 1
下面我们考虑几种特殊情况，来看上述代码是否也适用：
- 要删除的节点是链表的头节点：
我们直接返回head->next作为结果即可。 - 要删除的节点是链表的最后一个节点：
此时上述代码依旧适用。 - 要删除的节点既是链表的第一个节点又是最后一个节点，即链表只有一个节点：
返回NULL指针即可。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *p = head,*q = new ListNode(); q->next = p; int length = 0; while(p != NULL){ length++; p = p->next; } if(length == 1){ return NULL; } p = head; int count = length - n + 1; if(count == 1){ return head->next; } int number = 1; while(number < count){ q = p; p = p->next; number++; } q->next = p->next; return head; } };
- 1
- 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
- 28
上述的代码顺利解决问题，但是过多的if判断降低了代码的可读性，我们对于节点删除部分可以进行修改。在链表中，往往为了使对于链表的操作对于包括头节点的节点都适用，我们往往会构造一个虚拟节点，使其指向head节点，借此来将head节点也变成链表中的一个普通节点。然后我们进行找到链表的倒数第N+1个节点，直接使用p->next = p->next->next进行节点删除就可以，当要删除的节点是链表的头节点的时候，那么p就是我们构造的虚拟节点。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *p = head,*q = new ListNode(); q->next = p; int length = 0; while(p != NULL){ length++; p = p->next; } p = q; int count = length - (n + 1) + 1; int number = 1; while(number <= count){ p = p->next; number++; } p->next = p->next->next; return q->next; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
链表删除部分已经十分简单，遍历链表的时间复杂度也是
O
(
N
)
O(N)
O(N)，但是这样子操作不够优雅，对就是你想的那个elegant，其实我们寻找链表的倒数第N个节点的时候可以使用双指针的思想。
既然我们需要找倒数第N个节点，我们可以让两个指针fast、slow首先指向链表的头节点，然后让fast指针前进N步，这样两个指针之间的距离就是N，那么当fast节点到达链表的末尾，也就是NULL指针的时候，slow节点正好指向链表的倒数第N个节点。是不是十分的优雅呀！！！虽然也是遍历链表，但只用遍历一次，相比上面遍历两次出去就可以狠狠的装X了。
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *q = new ListNode(); q->next = head; //寻找倒数第N+1个节点 n = n + 1; ListNode *fast = q,*slow = q; while(n--){ fast = fast->next; } while(fast != NULL){ slow = slow->next; fast = fast->next; } slow->next = slow->next->next; return q->next; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
合并两个有序链表
思路：
我们使用两个指针，分别指向两个链表的头节点，然后比较大小，来构造一个新的链表。所以问题就转变为遍历链表，然后比较节点的大小，在根据比较结果来进行新链表的构造，也就是在链表的尾部不断插入新节点。我们使用cur指针指向链表的最后的最后一个节点，然后使用cur->next = p/q，再更改指针cur的指向，即cur = cur->next。
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *p = list1,*q = list2; ListNode *dummy = new ListNode(),*cur = dummy; while(p != NULL && q != NULL){ if(p->val < q->val){ cur->next = p; p = p->next; } else{ cur->next = q; q = q->next; } cur = cur->next; } if(p != NULL){ cur->next = p; } if(q != NULL){ cur->next = q; } return dummy->next; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
这道题是十分简单的，但是在提交的过程中发现了一个小知识点！！！当我的代码中是如下的时候会出错：
if(!p){
cur->next = p;
}
if(!q){
cur->next = q;
}
- 1
- 2
- 3
- 4
- 5
- 6
这下子真的阅读**《C和指针》**，书中有如下内容：
标准定义了NULL指针，它作为一个特殊的指针变量，表示不指向任何东西，要使一个指针变量为NULL，可以给它赋一个零值。为了测试一个指针变量是否为NULL，可以将其与零值进行比较。之所以选择零这个值，是因为一种源代码约定。就机器内部而言，NULL指针的实际值可能与此不同。在这种情况下，编译器将负责将零值和内部值之间的翻译转换。
咦？好奇怪呀，按理说应该可以判断呀，为什么会错呢？
原来我是个傻逼，按照逻辑应该写成if(p)和if(q)的。虚惊一场…
下面来欣赏官方大大的操作，官方采用的是递归的方法，可恶呀，又是递归，又是我没掌握的技能点：
{
l
i
s
t
1
[
0
]
+
m
e
r
g
e
(
l
i
s
t
1
[
1
:
]
,
l
i
s
t
2
)
l
i
s
t
1
[
0
]
<
l
i
s
t
2
[
0
]
l
i
s
t
2
[
0
]
+
m
e
r
g
e
(
l
i
s
t
1
,
l
i
s
t
2
[
1
:
]
)
o
t
h
e
r
w
i
s
e
\left\{
递归的终止条件即为两个链表中有任意一个为空即可停止，所以我们需要考虑边界情况，如果链表中有一个为空，那就将另一个链表的头节点作为结果进行返回。
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if(list1 == NULL){ return list2; } else if(list2 == NULL){ return list1; } else if(list1->val < list2->val){ list1->next = mergeTwoLists(list1->next, list2); return list1; } else{ list2->next = mergeTwoLists(list1,list2->next); return list2; } } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
看了代码，是不是依旧很迷糊，我也很迷糊，脑子转不动了，而且还要去背单词，那我只好交给明天的自己了，QAQ!
睡了一觉，神清气爽，然后好像就突然明白了递归的道理。我们判断l1、l2头节点哪一个更小，然后较小的节点的next指针指向其余节点的合并结果，递归的终止条件就是当两个链表一个为NULL的时候，终止递归。好像还是没有描述清楚QAQ，那就只好借鉴别的大佬了，这下清清楚楚明明白白了：
//(1,1):代表第一次进入递归函数，并且从第一个口进入，并且记录进入前链表的状态
merge(1,1): 1->4->5->null, 1->2->3->6->null
merge(2,2): 4->5->null, 1->2->3->6->null
merge(3,2): 4->5->null, 2->3->6->null
merge(4,2): 4->5->null, 3->6->null
merge(5,1): 4->5->null, 6->null
merge(6,1): 5->null, 6->null
merge(7): null, 6->null
return l2
l1.next — 5->6->null, return l1
l1.next — 4->5->6->null, return l1
l2.next — 3->4->5->6->null, return l2
l2.next — 2->3->4->5->6->null, return l2
l2.next — 1->2->3->4->5->6->null, return l2
l1.next — 1->1->2->3->4->5->6->null, return l1
递归程序还是难呀！写递归程序，不能深想，毕竟人脑不是计算机，很容易糊涂，完成一个递归程序还是应该主要关注以下几点：
- 这个问题的子问题是什么，也就是如何进行递归。
- 当前层要干什么事情。
- 递归出口。
合并K个升序链表
思路：
根据合并两个有序列表的经验，我们可以使用K个指针，分别用来遍历每一个链表来完成合并的操作，这样子操作的主要问题在于如何进行K个数据的比较，来决定首先插入哪一个节点，并且当某个链表遍历完成之后，我们不应该退出循环，因为还有其他K-1个链表需要我们继续遍历，这样子就会使得代码变得冗长，且极容易出错。
考虑到之前已经完成了合并两个有序链表，那么我们在解决这一道问题的时候，就可以采用迭代的方法，将问题转化为合并两个有序链表，但是需要合并K-1次。
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *p = list1,*q = list2; ListNode *dummy = new ListNode(),*cur = dummy; while(p != NULL && q != NULL){ if(p->val < q->val){ cur->next = p; p = p->next; } else{ cur->next = q; q = q->next; } cur = cur->next; } if(p != NULL){ cur->next = p; } if(q != NULL){ cur->next = q; } return dummy->next; } ListNode* mergeKLists(vector<ListNode*>& lists) { ListNode *ans = new ListNode(); ans = NULL; int k = lists.size(); if(k == 1) return lists[0]; for(int i = 1;i < k;i++){ ans = mergeTwoLists(lists[0],lists[i]); lists[0] = ans; } return ans; } };
- 1
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
虽然已经解决了这道题，但是这样子显得还是不够优雅，我们稍微稍微看了一下题解，便不得不震撼于别人的操作，其实大体思路是一样的，也是将链表两两进行合并，只不过我们需要合并K-1次，但是如果我们采用**分而治之**的思想，每次合并两个，就可以大大减小合并次数。经过第一轮合并，K个链表就变成了K/2个，再进行合并，就变成了K/4个，这就是我们的主要思路。那么我们如何进行实现呢？我们可以借鉴归并排序的思路，我们首先进行拆分，后面进行合并，只不过在归并排序中我们操作的是某一个数字，而在合并K个链表中，我们操作的是某一个链表，我们已经编写了合并两个链表的函数，所以这样子是完全可行的。
首先我们进行拆分，将K个链表拆分成K/2个，再将K/2个拆分成K/4个等等，最后再进行合并，先将K/4个合并为K/2个，再将K/2个合并K个，是不是有一点递归的感觉？
- 这个问题的子问题是什么，也就是如何进行递归？
子问题是将一组链表进行划分，然后进行合并。
- 当前层要干什么事情？
若链表还可以进行划分，则将链表左右半区分别进行划分，然后将划分后的结果进行合并。否则递归结束。
- 递归出口？
当子问题的链表个数变成1或者0的时候，进行返回，如果只剩一个链表，那么将该链表进行返回，如果只剩下0个链表，那么返回空指 针即可。
明晰以上问题之后，我们来进行代码的撰写：
class Solution { public: //合并两个有序链表 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *p = list1,*q = list2; ListNode *dummy = new ListNode(),*cur = dummy; while(p != NULL && q != NULL){ if(p->val < q->val){ cur->next = p; p = p->next; } else{ cur->next = q; q = q->next; } cur = cur->next; } if(p != NULL){ cur->next = p; } if(q != NULL){ cur->next = q; } return dummy->next; } ListNode* merge(vector <ListNode*> &lists, int l, int r) { //只有一个链表 if (l == r) return lists[l]; //没有链表 if (l > r) return nullptr; //找中间点 int mid = (l + r) >> 1; //递归划分左半区 ListNode *left = merge(lists,l,mid); //递归划分右半区 ListNode * right = merge(lists,mid+1,r); //将左右半区进行合并 return mergeTwoLists(left, right); } ListNode* mergeKLists(vector<ListNode*>& lists) { return merge(lists, 0, lists.size() - 1); } };
- 1
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
现在已经大功告成了！！！等等，不对，我们的标题是使用双指针进行链表问题的解决，这两种方法都没有用到双指针的思想呀，而用到双指针思想的方法被我们第一个判处了死刑。看了题解发现，我们之前觉得获得链表K个节点的最小值很麻烦，但是当我们用到一种名叫**优先级队列（二叉堆）**这种数据结构的时候，我们的问题便迎刃而解。
我们先copy一下官方的代码：
class Solution { public: struct Status { int val; ListNode *ptr; bool operator < (const Status &rhs) const { return val > rhs.val; } }; priority_queue <Status> q; ListNode* mergeKLists(vector<ListNode*>& lists) { for (auto node: lists) { if (node) q.push({node->val, node}); } ListNode head, *tail = &head; while (!q.empty()) { auto f = q.top(); q.pop(); tail->next = f.ptr; tail = tail->next; if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next}); } return head.next; } };
- 1
- 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
这一段代码中蕴含了许多不太懂的知识点，我们来逐步进行分析与学习。
首先是关于const修饰符，其主要用途有两个：
- 常量类型限定符：声明一个常量，表示变量的值不可以进行修改。
- const-qualified member functions：该成员函数不会修改调用它的对象，也就是说，这个函数承诺不会对对象的状态进行修改。如果一个成员函数被声明为
const，它就被认为是一个常量成员函数，不能修改类的成员变量（非mutable变量），也不能调用非常量成员函数，以确保它不会对对象的状态进行改变。在类的成员函数后面加上const关键字，可以使这个函数成为一个常量成员函数。
bool operator < (const Status &rhs) const {
return val > rhs.val;
}
- 1
- 2
- 3
重载<运算符，返回类型为bool类型，函数名称为operator <(重载运算符函数名称的时候operator后面这个空格是可有可无的)，函数的形参是一个const Status &rhs，也就是一个引用变量，但用const进行修饰，表明不会对改变量进行修改。后面的const则表明这是一个常量成员函数，不会对调用它的对象的状态进行修改。
然后我们再来学习C++中的优先队列(以下内容来自cpp reference)：
//定义在头文件<queue>
std::priority_queue
template<
class T,class Container = std::vector<T>,class Compare = std::less<typename Container::value_type>
> class priority_queue
- 1
- 2
- 3
- 4
- 5
优先队列是一种容器适配器，它可以在常数时间内查找到最大的元素（默认），但是以对数的复杂度插入和提取为代价。用户可以通过修改Compare来改变顺序，比如使用std::greater<T>可以让最小的元素出现在最顶部。使用优先队列与管理随机访问容器的堆相似，但好处是不会意外地使堆无效化。
模板参数：
-
T：存储元素的类型，如果
T与Container::value_type的类型不一致，其表现是udefined。 -
Container：用来存储元素的底层容器类型。这个容器必须满足
SequenceContainer的要求，并且它的迭代器必须满足LegacyRandomAccessIterator的要求。此外，它必须提供以下函数作为通常语义：- front()
- push_back()
- pop_back()
标准容器
std::vector（包含std::vector<bool>）和std::deque满足这些要求。 -
Compare：一个提供严格弱排序的Compare类型。需要注意的是，
Compare参数定义为如果它的第一个参数在弱排序（允许相等）中在第二个参数之前，它返回true。但是因为优先队列首先输出最大的元素，因此位于之前的元素实际上是最后输出的。也就是说，队列的前端包含根据Compare提供的弱排序的“最后”元素。
对于自定义类型如何使用优先队列：
//1.运算符重载 struct tmp1 //运算符重载< { int x; tmp1(int a) {x = a;} bool operator<(const tmp1& a) const { return x < a.x; //大顶堆 } }; //2.重写仿函数 /*这意味着你可以像调用函数一样使用这个类的实例，即将对象当作函数来调用。仿函数通常用于自定义排序、搜索、转换等操作，可以作为函数指针的替代，非常灵活。通常，仿函数的实例可以接受参数，并返回一个结果，就像普通的函数一样。*/ struct tmp2 //重写仿函数 { bool operator() (tmp1 a, tmp1 b) { return a.x < b.x; //大顶堆 } }; int main() { tmp1 a(1); tmp1 b(2); tmp1 c(3); priority_queue<tmp1> d; d.push(b); d.push(c); d.push(a); while (!d.empty()) { cout << d.top().x << '\n'; d.pop(); } cout << endl; priority_queue<tmp1, vector<tmp1>, tmp2> f; f.push(c); f.push(b); f.push(a); while (!f.empty()) { cout << f.top().x << '\n'; f.pop(); } } /*———————————————— 版权声明：本文为CSDN博主「吕白_」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/weixin_36888577/article/details/79937886*/
- 1
- 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
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
分隔链表
思路：
这道题还是比较容易的。既然我们要依据一个值来将链表分割成两个部分，前面的部分小于这个值，后面的部分大于这个值，并且要保证这些节点在链表中原有的顺序。所以我们很容易想到使用两个指针，一个指针用来将比这个值小的节点串起来形成一个链表，一个指针用来将比这个值大的节点串起来形成一个链表，最后再将值小的链表的最后一个节点的next指向值大的链表的头节点，同时要注意将最后一个节点的指针改为nullptr即可。
class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode *less =new ListNode(),*greater =new ListNode(),*temp = head; ListNode *p = less,*q = greater; for(;temp != NULL;temp = temp->next){ if(temp->val < x ){ less->next = temp; less = less->next; } else{ greater->next = temp; greater = greater->next; } } greater->next = nullptr; less->next = q->next; return p->next; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
链表的中间节点
876. Middle of the Linked List
思路：
如果我们的处理对象是数组而不是链表，那么这个问题十分简单，但是由于单链表只能从前往后进行遍历，我们只有遍历一遍才能得知链表的长度，然后我们再从头进行遍历，并设置一个计数器，从而可以来判断目前遍历的节点是不是链表的中间节点。上面这种方法显然可以解决问题，但是不够优雅，需要遍历两次链表，所以我们可以使用双指针来解决这个问题。我们初始化两个指针都指向链表的头节点，然后一个指针一次走两步，一个指针一次走一步，当每次走两步的那个指针到达链表末尾的时候，即fast->next = nullptr的时候，这个慢的指针会走到哪呢？
- 链表长度为奇数：我们假设链表长度为$2 \times n + 1 $，那么当一个指针走到链表的结尾即最后一个节点的时候，此时一共需要走$2 \times n
步，即循环一共进行
步，即循环一共进行
步，即循环一共进行n
次，那么此时慢指针走到了第
次，那么此时慢指针走到了第
次，那么此时慢指针走到了第n + 1$个节点，我们返回
slow即可； - 链表长度为偶数：我们假设链表长度为$2 \times n $，那么当快指针走到链表的结尾的
next指针，即访问到nullptr指针的时候，此时一共需要走 2 × n 2 \times n 2×n步，即循环一共进行 n n n次，那么此时慢指针走到了第 n + 1 n + 1 n+1个节点，我们返回slow即可；
经典的快慢指针！！！
