算法笔记学习-链表
原创
巧妙的构造虚拟头结点。可以使遍历处理逻辑更加统一；
灵活使用递归。构造递归条件，使用递归可以巧妙的解题。不过需要注意有些题目不能使用递归，因为递归深度太深会导致超时和栈溢出。
一、链表逆序
leetcode第92题：https://leetcode-cn.com/problems/reverse-linked-list-ii/
//本次步骤如下：
//（1）先设置一个虚拟头节点，避免判断边界条件
//（2）设置三个指针，一个指向left，一个指向left前面的节点(a)， 一个指向left后面的节点（b)
//（3）指向left的节点，和指向left后面的节点一起循环移动，移动的过程中,调换指针指向方向，具体看代码
//（4）循环终止条件就是left的节点到达right,
ListNode* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(-1), *h = dummy;
dummy->next = head;
for (int i = 0; i < left - 1; i ++, h = h->next);
ListNode* a = h->next, *b = a->next;//设置那三个指针
right -= left;//循环条件
while (right > 0){
right --;
ListNode* tmp = b->next;
b->next = a;//调换方向
a = b;
b = tmp;//a, b指针继续向后挪一个位置
}
h->next->next = b;//h本来是指向a的，现在a是最后一个right节点，因此这个节点要执行原来right之后的一个节点
h->next = a; //指向逆序后的right节点；
return dummy->next;
}二、寻找链表节点
这一类题目最容易想到的解法一应该就是双指针了
1、leetcode第876题：https://leetcode-cn.com/problems/middle-of-the-linked-list/
//寻找中间节点应该是最简单的了，只要设置两个指针fast和slow指针，fast指针每次走两个位置，slow指针每次走一个位置
//当fast指针走到最后的时候，也就是中间节点；
ListNode* middleNode(ListNode* head) {
ListNode *quick = head, *slow = head;
//1 2 3 4 5 6
while (quick->next){
quick = quick->next;
if (quick->next){
quick = quick->next;
}
slow = slow->next;
}
return slow;
}
这应该是一种特解了，下面来看看通解’
2、leetcode第19题：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
//像这种删除倒数第几个节点，在倒数第几个节点前面插入节点，输出倒数第几个节点的值都可以用下面的解法
//（1）先设置虚拟头节点
//（2）设置一个移动节点first指向原本的头节点，让其移动n个位置，，这个时候，然后first和虚拟头节点一起向后移动，
//（3）当first=nullptr，第二个指针指向的位置就是倒数第n个节点前面的节点；之后就可以进行删除，插入，查询操作了
ListNode* removeNthFromEnd(ListNode* head, int n) {
//0 1 2 3 4 5
ListNode* dummy = new ListNode(0, head);
ListNode* first = head;
ListNode* second = dummy;
for (int i = 0; i < n; i++){
first = first->next;
}
while (first){
first = first->next;
second = second->next;
}
second->next = second->next->next;
return dummy->next;
}三、合并链表
1、leetcode第21题：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
//合并两个链表是合并多个n个链表的基础，这里合并只新创建一个虚拟头节点，其他的在原先的两个链表上操作；
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode();
ListNode* head = l3;
while (l1 && l2){
if (l1->val >= l2->val){
l3->next = l2;
l3 = l2;
l2 = l2->next;
}else{
l3->next = l1;
l3 = l1;
l1 = l1->next;
}
}
if (l1){
l3->next = l1;
}
if (l2){
l3->next = l2;
}
return head->next;
}2、leetcode第23题：https://leetcode-cn.com/problems/merge-k-sorted-lists/
//这种合并k个链表的，要用到合并思想，把k个拆成两两合并
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* l3 = new ListNode();
ListNode* head = l3;
while (l1 && l2){
if (l1->val >= l2->val){
l3->next = l2;
l3 = l2;
l2 = l2->next;
}else{
l3->next = l1;
l3 = l1;
l1 = l1->next;
}
}
if (l1){
l3->next = l1;
}
if (l2){
l3->next = l2;
}
return head->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 - l) >> 1);
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists1(vector<ListNode*>& lists){
return merge(lists, 0, lists.size() - 1);
}
四、链表归类
1、leetcode第86题：https://leetcode-cn.com/problems/partition-list/
//链表归类，最容易想到的方法应该是分割之后再合并
ListNode* partition(ListNode* head, int x) {
//先分割再拼接
ListNode* dummy = new ListNode();
dummy->next = head;
ListNode* bigInX = new ListNode(), *p = bigInX;
ListNode* smallInX = new ListNode(), *q = smallInX;
while (head){
if (head->val >= x){
bigInX->next = head;
bigInX = head;
}else{
smallInX->next = head;
smallInX = head;
}
head = head->next;
}
smallInX->next = p->next;
bigInX->next = nullptr;
return q->next;
}
//也可以再原有的空间上操作，，设置一个尾节点，符合条件就移动到尾节点后，然后把该节点设置成尾节点
ListNode* partition1(ListNode* head, int x) {
ListNode* dummy = new ListNode(), *h = dummy;
if (head == nullptr)return nullptr;
dummy->next = head;
ListNode* p = head;
while (p->next){
p = p->next;
}
ListNode* tail = p, *q = tail;
p = head;
while (p != q->next){
if(p->val >= x){
tail->next = p;
h->next = p->next;
p = p->next;
tail = tail->next;
}else{
p = p->next;
h = h->next;
}
}
tail->next = nullptr;
return dummy->next;
}2、leetcode第328题：https://leetcode-cn.com/problems/odd-even-linked-list/
//跟上面题目是一样的
ListNode* oddEvenList(ListNode* head) {
ListNode* odd = new ListNode();
ListNode* even = new ListNode();
ListNode* oddTail = odd;
ListNode* evenTail = even;
int i = 1;
while (head){
if (i & 1){
oddTail->next = head;
oddTail = head;
}else{
evenTail->next = head;
evenTail = head;
}
head = head->next;
i ++;
}
oddTail->next = even->next;
evenTail->next = nullptr;
return odd->next;
}五、判断链表是否有环，有交点
1、leetcode第141题：https://leetcode-cn.com/problems/linked-list-cycle/
2、leetcode第142题：https://leetcode-cn.com/problems/linked-list-cycle-ii/
这一类题目只要分为两类，判断是否有环，判断哪个是进环的第一个节点；
（1）判断是否有环，只要设置两个指针，然后让一个指针每次走两个，一个每次走一个，，如果之后两个指针能相遇，则说明有环；
（2）而找出哪个是进环的第一个节点这样是远远不够的，，比如：假设非环部分长度为a,环部分长度为b，如果两者相遇，那必然是快指针走的位置为慢指针的两倍，，如果a = b 那第一次相遇就是入环第一个节点，那是特殊情况，所以我们要在第一次相遇后，，让快指针从头节点重新再走一次，慢指针仍然继续走，，这是为了人快指针比慢指针夺走这个a，这样相遇必然是在入环第一个节点
//判断是否有环
public:
bool hasCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
while (true){
if (fast == nullptr || fast->next == nullptr)return false;
fast = fast->next;
if (fast != nullptr)
fast = fast->next;
slow = slow->next;
if (slow == fast)return true;
}
return false;
}
//找出入环的第一个节点
ListNode* detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (true){
if (fast == nullptr || fast->next == nullptr)return nullptr;
fast = fast->next;
if (fast){
fast = fast->next;
}
slow = slow->next;
if (fast == slow)break;
}
fast = head;
while (fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}六、链表排序
这个就比较单纯了，只能用归并排序
1、leetcode第148题：
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head, ListNode* tail) {
if (head == nullptr) {
return head;
}
if (head->next == tail) {
head->next = nullptr;
return head;
}
ListNode* slow = head, *fast = head;
while (fast != tail) {
slow = slow->next;
fast = fast->next;
if (fast != tail) {
fast = fast->next;
}
}
ListNode* mid = slow;
return merge(sortList(head, mid), sortList(mid, tail));
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录