labuladong刷题笔记一（单链表）

目录

一、单链表

1.单链表的六大解题套路，你都见过么？ 

（1）21. 合并两个有序链表 

（2）23. 合并K个升序链表

（3）19. 删除链表的倒数第 N 个结点

（4）876. 链表的中间结点

（5）141. 环形链表 

（6）160. 相交链表 

2.递归反转链表：如何拆解复杂问题 

（1）206. 反转链表(递归)

（2）92. 反转一部分链表 （递归）

3.递归思维：k 个一组反转链表 

（1）25. K 个一组翻转链表 （迭代）

4.经典面试题：最长回文子串

（1）125. 验证回文串

（2）5. 最长回文子串

5.如何高效判断回文单链表？ 

（1）234. 回文链表 

        p->next=p1：表示节点p的下一个节点是p1

        p=p->next：表示向前移动，修改指针p的位置，把p指向原来的下一个节点。

        优先队列

        快慢指针

        快慢指针

        快慢指针

注意这段代码：p1永远都不会是nullptr

if(p1->next)
{
    p1=p1->next;
}
else{
    p1=headB;
}

    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)
        {
            return nullptr;
        }
        if(head->next==nullptr)
        {
            return head;
        }
        ListNode* node=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return node;
    }

    struct ListNode {
        int val;
        ListNode *next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode *next) : val(x), next(next) {}
    };

    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(left==1)
        {
            return reverseN(head,right);
        }
        head->next=reverseBetween(head->next,left-1,right-1);
        return head;
    }
    //反转前n个结点
    ListNode* successor=nullptr;
    ListNode* reverseN(ListNode* head,int n)
    {
        if(head==nullptr)
        {
            return nullptr;
        }
        if(n==1||head->next==nullptr)
        {
            successor=head->next;
            return head;
        }
        ListNode* last=reverseN(head->next,n-1);
        head->next->next=head;
        head->next=successor;
        return last;
    }

class Solution {
public:
    int i=0;

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *a = head , *b = head ;
        ListNode *myNode=new ListNode(-1);
        ListNode *p=myNode;
        if(!head||!head->next)
        {
            return head;
        }

        while(i < k && b)
        {
            b=b->next;
            ++i;
            if(i==k)
            {
                myNode->next = reverse(a,b);
                for(int j=0;jnext->val<next;
                }
                a=b;
                i=0;
            }
            else if(b==nullptr)
            {
                myNode->next=a;
            }
        }
        return p->next;

    }

    //反转a与b之间的结点[a,b]
    ListNode* reverse(ListNode* a,ListNode* b)
    {
        ListNode *currentNode=a,
                *lastNode=nullptr,
                *nextNode=nullptr;
        while(currentNode!=b)
        {
            nextNode=currentNode->next;
            currentNode->next=lastNode;
            lastNode=currentNode;
            currentNode=nextNode;
        }
        cout<<"lastnode:"<val<

#include 
std::transform(s.begin(), s.end(), s.begin(), toupper);