目录
1.21. 合并两个有序链表 - 力扣（LeetCode）
我做过啊，为什么还是不能独立做出来，为什么为什么啊啊啊 嘻嘻奔向五一
是这样的：
要按升序连接，以链表2头结点作为开端，哪个小就先连接哪个，然后把此时操作的链表的指针往后移，同时遍历新链表的指针也要往后移
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *head = new ListNode(0);
ListNode *p = head;
while(list1 && list2){
// 如果list2的元素大于list1的元素，就先把list1的元素加入到新链表中
if(list2->val > list1->val){
p->next = list1;
list1 = list1->next;
}
else{
// 如果list2的元素小于等于list1的元素，就先把list2的元素加入到新链表中
p->next = list2;
list2 = list2->next;
}
p = p->next;
}
// 因为两个链表都是有序的，谁先遍历完了，另一个没有遍历玩的直接全部接上去就好
p->next = list1 ? list1: list2;
return head->next;
}
};2.86. 分隔链表 - 力扣（LeetCode）
这个思路是这样的，把大于x的元素放在一个链表中名为large，把小于x的元素放在一个链表中，名为small，等到最后题目给出的链表遍历完了，把large接到small的后面返回。
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode *smallHead = new ListNode(0);
ListNode *small = smallHead;
ListNode *largeHead = new ListNode(0);
ListNode *large = largeHead;
while(head){
if(head->val < x){
small->next = head;
small = small->next;
}
else{
large->next = head;
large = large->next;
}
head = head->next;
}
large->next = nullptr;
small->next = largeHead->next;
return smallHead->next;
}
};3.141. 环形链表 - 力扣（LeetCode）
是环形链表2的简化
可以想象成龟兔赛跑，在一个链表中，兔子每次走两步，乌龟每次走一步。如果这个链表没有环的话，那么乌龟兔子最后肯定都会走到空指针，并且兔子先走到。如果这个链表有环的话，那么兔子先进入环中，不断地绕环走绕环走，肯定会等到乌龟进入环中并且相遇。这时候兔子就说：因为我知道你会来，所以我等。哈哈哈哈哈哈哈哈哈哈哈哈哈哈
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head;
ListNode *slow = head;
while(fast && fast->next){
if(slow == nullptr || fast == nullptr){
return false;
}
fast = fast->next->next;
slow = slow->next;
}
return true;
}
};fast->next检查也是为在fast移动两步之前，确保下一步是安全的。
4.876. 链表的中间结点 - 力扣（LeetCode）
求链表长度，首位相连，定位，返回。
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int len = 1;
ListNode *p = head;
while(p->next){
len++;
p = p->next;
}
// 跳出循环时，p指向的是链表的最后一个结点的下一个结点，而不是最后一个结点
p = head;
// 要定位到断开结点的前一个结点 类似于删除
int mid = 0;
while(mid < n / 2){
mid++;
p = p->next;
}
return p;
}
};
