链表

定义

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）

链表中的节点在内存中不是连续分布的，是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理

• 双链表

• 循环链表

• 定义链表

//单链表(C++)
struct ListNode {
    int val;//节点上存储的元素
    ListNode *next;//指向下一个节点的指针
    ListNode(int x):val(x),next(NULL){}//节点的构造函数
};
//单链表(C)
typedef struct ListNodeT {
    int val;
    struct ListNodeT next;
}ListNode;

• 性能分析

	插入/删除 （时间复杂度）	查询 （时间复杂度）	适用场景
数组	O(n)	O(1)	数据量固定，频繁查询，较少增删
链表	O(1)	O(n)	数据量不固定，频繁增删，较少查询

移除链表元素

203. 移除链表元素

直接删除

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while(head!=NULL&&head->val==val){//不是if防止链表元素都是val
            ListNode*tmp=head;//释放空间
            head=head->next;
            delete tmp;
        }
        ListNode* slt=head;
        while(slt!=NULL&&slt->next!=NULL){
            if(slt->next->val==val){
                ListNode*tmp=slt->next;
                slt->next=slt->next->next;
                delete tmp;
            }else{
                slt=slt->next;
            }
        }
        return head;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

设置一个虚拟头结点

统一了移除链表头结点和其他结点的方式，最后return dummyNode->next

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyNode=new ListNode(0);
        dummyNode->next=head;
        ListNode* slt=dummyNode;
        while(slt!=NULL&&slt->next!=NULL){
            if(slt->next->val==val){
                ListNode*tmp=slt->next;
                slt->next=slt->next->next;
                delete tmp;
            }else{
                slt=slt->next;
            }
        }
        return dummyNode->next;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

递归法

基础情况：对于空链表，不需要移除元素

递归情况：首先检查头节点的值是否为val，如果是则移除头节点，答案即为在头节点的后续节点上递归的结果；如果头节点的值不为val，则答案为头节点与在头节点的后续节点上递归得到的新链表拼接的结果

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        //基础情况：空链表
        if(head==nullptr){
            return nullptr;
        }

        //递归处理
        if(head->val==val){
            ListNode* newHead=removeElements(head->next,val);
            delete head;
            return newHead;
        }else{
            head->next=removeElements(head->next,val);
            return head;
        }
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

设计链表

707. 设计链表

单链表

delete

class MyLinkedList {
public:
    struct LinkNode{
        int val;
        LinkNode* next;
        LinkNode(int val):val(val),next(nullptr){}
    };

    MyLinkedList() {
        size=0;
        dummyHead=new LinkNode(0);
    }
    
    int get(int index) {
        if(index<0||index>(size-1)){
            return -1;
        }
        LinkNode* slt=dummyHead->next;
        while(index--){
            slt=slt->next;
        }
        return slt->val;
    }
    
    void addAtHead(int val) {
        LinkNode* newheadnode=new LinkNode(val);
        newheadnode->next=dummyHead->next;
        dummyHead->next=newheadnode;
        size++;
    }
    
    void addAtTail(int val) {
        LinkNode* newtailnode=new LinkNode(val);
        LinkNode* slt=dummyHead;
        while(slt->next!=nullptr){
            slt=slt->next;
        }
        slt->next=newtailnode;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            index=0;
        }
        LinkNode* newnode=new LinkNode(val);
        LinkNode* slt=dummyHead;
        while(index--){
            slt=slt->next;
        }
        newnode->next=slt->next;
        slt->next=newnode;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index>size||index<0){
            return;
        }
        LinkNode* slt=dummyHead;
        while(index--){
            slt=slt->next;
        }
        LinkNode* tmp=slt->next;
        slt->next=slt->next->next;
        delete tmp;
        //注意及时赋予nullptr！
        tmp=nullptr;
        size--;
    }
    void printMyLinkedList(){
        LinkNode* slt=dummyHead;
        while(slt->next!=nullptr){
            cout<<slt->next->val<<" ";
            slt=slt->next;
        }
        cout<<endl;
    }
private:
    int size;
    LinkNode* dummyHead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

• 时间复杂度：涉及index的相关操作为O(index)，其余为O(1)
• 空间复杂度：O(n)

双链表

• addAtHead额外new tmp

class MyLinkedList {
public:
    struct DList{
        int info;
        DList* llink;
        DList* rlink;
        DList(int info):info(info),llink(nullptr),rlink(nullptr){};
    };

    MyLinkedList() {
        size=0;
        sentinelnode=new DList(0);//创建哨兵节点，不存储有效数据
        sentinelnode->rlink=sentinelnode;
        sentinelnode->llink=sentinelnode;
    }
    
    int get(int index) {
        if(index<0||index>(size-1)){
            return -1;
        }
        int mid=size>>1;//计算链表中部位置
        DList* slt=sentinelnode;
        if(index<mid){//从前往后遍历
            for(int i=0;i<index+1;i++){
                slt=slt->rlink;
            }
        }else{//从后往前遍历
            for(int i=0;i<size-index;i++){
                slt=slt->llink;
            }
        }
        return slt->info;
    }
    
    void addAtHead(int val) {
        DList* newnode=new DList(val);
        DList* next=sentinelnode->rlink;
        newnode->llink=sentinelnode;
        newnode->rlink=next;
        size++;
        sentinelnode->rlink=newnode;
        next->llink=newnode;
    }
    
    void addAtTail(int val) {
        DList* newnode=new DList(val);
        DList* pre=sentinelnode->llink;
        newnode->llink=pre;
        newnode->rlink=sentinelnode;
        size++;
        sentinelnode->llink=newnode;
        pre->rlink=newnode;
    }
    
    void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<=0){
            addAtHead(val);
            return;
        }
        int mid=size>>1;
        DList* slt=sentinelnode;
        DList* newnode=new DList(val);
        if(index<mid){
            for(int i=0;i<index;i++){//从前往后遍历，注意这里没有+1
                slt=slt->rlink;
            }
            DList* tmp=slt->rlink;//tmp对应第n个节点
            slt->rlink=newnode;
            tmp->llink=newnode;
            newnode->rlink=tmp;
            newnode->llink=slt;
        }else{
            for(int i=0;i<size-index;i++){//从后往前遍历
                slt=slt->llink;
            }
            DList* tmp=slt->llink;
            slt->llink=newnode;
            tmp->rlink=newnode;
            newnode->llink=tmp;
            newnode->rlink=slt;
        }
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>(size-1)){
            return;
        }
        int mid=size>>1;
        DList* slt=sentinelnode;
        if(index<mid){
            for(int i=0;i<index;i++){
                slt=slt->rlink;
            }
            DList* next=slt->rlink->rlink;
            delete slt->rlink;
            slt->rlink=next;
            next->llink=slt;
        }else{
            for(int i=0;i<size-index-1;i++){//注意-1
                slt=slt->llink;
            }
            DList* pre=slt->llink->llink;
            slt->llink=pre;
            delete pre->rlink;
            pre->rlink=slt;
        }
        size--;
    }
private:
    int size;
    DList* sentinelnode;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

• addAtHead直接add

class MyLinkedList {
public:
    struct DList{
        int info;
        DList* llink;
        DList* rlink;
        DList(int info):info(info),llink(nullptr),rlink(nullptr){};
    };

    MyLinkedList() {
        size=0;
        sentinelnode=new DList(0);//创建哨兵节点，不存储有效数据
        sentinelnode->rlink=sentinelnode;
        sentinelnode->llink=sentinelnode;
    }
    
    int get(int index) {
        if(index<0||index>(size-1)){
            return -1;
        }
        int mid=size>>1;//计算链表中部位置
        DList* slt=sentinelnode;
        if(index<mid){//从前往后遍历
            for(int i=0;i<index+1;i++){
                slt=slt->rlink;
            }
        }else{//从后往前遍历
            for(int i=0;i<size-index;i++){
                slt=slt->llink;
            }
        }
        return slt->info;
    }
    
    void addAtHead(int val) {
        DList* newnode=new DList(val);
        DList* next=sentinelnode->rlink;
        newnode->llink=sentinelnode;
        newnode->rlink=next;
        size++;
        sentinelnode->rlink=newnode;
        next->llink=newnode;
    }
    
    void addAtTail(int val) {
        DList* newnode=new DList(val);
        DList* pre=sentinelnode->llink;
        newnode->llink=pre;
        newnode->rlink=sentinelnode;
        size++;
        sentinelnode->llink=newnode;
        pre->rlink=newnode;
    }
    
    void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<=0){
            addAtHead(val);
            return;
        }
        int mid=size>>1;
        DList* slt=sentinelnode;
        DList* newnode=new DList(val);
        if(index<mid){
            for(int i=0;i<index;i++){//从前往后遍历，注意这里没有+1
                slt=slt->rlink;//slt
            }
            //后插
            newnode->rlink=slt->rlink;
            newnode->llink=slt;
            slt->rlink->llink=newnode;
            slt->rlink=newnode;
        }else{
            for(int i=0;i<size-index;i++){//从后往前遍历
                slt=slt->llink;
            }
            //前插
            newnode->rlink=slt;
            newnode->llink=slt->llink;
            slt->llink->rlink=newnode;
            slt->llink=newnode;
        }
        size++;
    }
    
    void deleteAtIndex(int index) {
        if(index<0||index>(size-1)){
            return;
        }
        int mid=size>>1;
        DList* slt=sentinelnode;
        if(index<mid){
            for(int i=0;i<index;i++){
                slt=slt->rlink;
            }
            DList* next=slt->rlink->rlink;
            delete slt->rlink;
            slt->rlink=next;
            next->llink=slt;
        }else{
            for(int i=0;i<size-index-1;i++){//注意-1
                slt=slt->llink;
            }
            DList* pre=slt->llink->llink;
            slt->llink=pre;
            delete pre->rlink;
            pre->rlink=slt;
        }
        size--;
    }
private:
    int size;
    DList* sentinelnode;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

反转链表

206. 反转链表

双指针法

链表逆置详细讲解（图文）

当slt为空的时候循环结束，不断将slt指向pre

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* tmp;
        ListNode* slt=head;
        ListNode* pre=nullptr;
        while(slt){
            tmp=slt->next;
            slt->next=pre;
            pre=slt;
            slt=tmp;
        }
        return pre;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

递归法

• 从前往后

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(NULL,head);
    }
    ListNode* reverse(ListNode* pre,ListNode* slt){
        if(slt==NULL){
            return pre;
        }
        ListNode* tmp=slt->next;
        slt->next=pre;
        return reverse(slt,tmp);
    }
};

• 时间复杂度：O(n)，要递归处理链表的每个节点

• 空间复杂度：O(n)，递归调用了n层栈空间

• 从后往前

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL){
            return NULL;
        }
        if(head->next==NULL){
            return head;
        }
        //递归调用，翻转第二个节点开始往后的链表
        ListNode* last=reverseList(head->next);
        //翻转头节点与第二个节点的指向
        head->next->next=head;
        //此时的head节点为尾节点，next需要指向NULL
        head->next=NULL;
        return last;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

两两交换链表中的节点

24. 两两交换链表中的节点

交换相邻两个元素时建议一定要画图，搞清操作指针的前后顺序

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* slt=dummyHead;
        while(slt->next!=nullptr&&slt->next->next!=nullptr){
            ListNode* tmp=slt->next;
            ListNode* tmp1=slt->next->next->next;
            slt->next=slt->next->next;
            slt->next->next=tmp;
            slt->next->next->next=tmp1;
            slt=slt->next->next;
        }
        return dummyHead->next;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

删除链表的倒数第N个节点

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

双指针的经典应用

如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了

fast首先走n+1步

这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* slow=dummyHead;
        ListNode* fast=dummyHead;
        while(n--&&fast!=nullptr){
            fast=fast->next;
        }
        fast=fast->next;//fast再走一步使slow指向删除节点的上一个节点
        while(fast!=nullptr){
            fast=fast->next;
            slow=slow->next;
        }
        ListNode *tmp=slow->next;
        slow->next=slow->next->next;
        delete tmp;
        return dummyHead->next;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

相交链表

160. 相交链表

求出两个链表的长度，并求出两个链表长度的差值，然后让slta移动到和sltb末尾对齐的位置

此时我们就可以比较slta和sltb是否相同，如果不相同，同时向后移动slta和sltb，如果遇到slta==sltb，则找到交点，否则循环退出返回空指针

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* slta=headA;
        ListNode* sltb=headB;
        int lena=0,lenb=0;
        while(slta!=nullptr){
            lena++;
            slta=slta->next;
        }
        while(sltb!=nullptr){
            lenb++;
            sltb=sltb->next;
        }
        slta=headA;
        sltb=headB;
        if(lenb>lena){//让slta为最长链表的头
            swap(lena,lenb);
            swap(slta,sltb);
        }
        int gap=lena-lenb;
        while(gap--){
            slta=slta->next;
        }
        while(slta!=nullptr){
            if(slta==sltb){
                return slta;
            }
            slta=slta->next;
            sltb=sltb->next;
        }
        return nullptr;
    }
};

• 时间复杂度：O(n+m)
• 空间复杂度：O(1)

环形链表II

142. 环形链表 II

• 判断链表是否有环

使用快慢指针法，分别定义fast和slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果fast和slow指针在途中相遇，说明这个链表有环

• 找到这个环的入口

假设从头结点到环形入口节点的节点数为x。环形入口节点到fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为z

相遇时slow指针走过了x+y，fast指针走过了x+y+n(y+z)

n为fast在环内走了n圈遇到slow指针

有关系fast走的节点是slow的两倍，此时(x+y)*2=x+y+n(y+z)

得到x=n(y+z)-y，提出一个y+z，整理得x=(n-1)(y+z)+z

• n为1

fast指针在环形里转了一圈就遇到了slow指针，此时x=z

有：从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点

可在相遇节点处，定义一个指针index1，在头结点处定一个指针index2

index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点

• n>1

fast指针在环形转n圈之后才遇到slow指针

此时index1指针在环里多转了(n-1)圈然后再遇到index2，相遇点依然是环形的入口节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast!=nullptr&&fast->next!=nullptr){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                ListNode* index1=fast;
                ListNode* index2=head;
                while(index1!=index2){
                    index1=index1->next;
                    index2=index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};

• 时间复杂度：O(n)

  快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个index指针走的次数也小于链表长度，总体为走的次数小于2n

• 空间复杂度：O(1)