代码随想录 (programmercarl.com)

一、链表种类

1. 单链表

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

2. 双指针

单链表中的指针域只能指向节点的下一个节点。

双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。

双链表 既可以向前查询也可以向后查询。

3. 循环链表

循环链表，顾名思义，就是链表首尾相连。

循环链表可以用来解决约瑟夫环问题。

二、链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。

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

如图所示：

三、链表的实现

707.设计链表

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

    MyLinkedList() {
        head=new ListNode(0);
        size=0;
    }

    int get(int index) {
        if(index>=size || index<0) return -1;
        ListNode* p=head->next;
        while(index--) p=p->next;
        return p->val;
    }

    void addAtHead(int val) {
        ListNode* p=new ListNode(val);
        p->next=head->next;
        head->next=p;
        size++;
    }

    void addAtTail(int val) {
        ListNode* p=head;
        while(p->next!=nullptr) p=p->next;
        ListNode* q=new ListNode(val);
        p->next=q;
        size++;
    }

    void addAtIndex(int index, int val) {
        if(index>size || index<0) return;
        ListNode* p=head;
        while(index--) p=p->next;
        ListNode* q=new ListNode(val);
        q->next=p->next;
        p->next=q;
        size++;
    }

    void deleteAtIndex(int index) {
        if(index>=size || index<0) return;
        ListNode* p=head;
        while(index--) p=p->next;
        ListNode* q=p->next;
        p->next=q->next;
        delete q;
        q=nullptr;
        size--;
    }

private:
    ListNode* head;
    int size;

};

1. 链表的定义

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

ListNode *head=new ListNode();

2. 新增结点

一般采用头插法，头结点为虚拟结点（避免边界）。

void addNode(int val) {
    ListNode *newNode=new ListNode(val);
    newNode->next=head->next;
    head->next=newNode;
}

3. 删除结点

void deleteAtIndex(int index) {
    ListNode* p=head;
    while(index--){
	    if(p==nullptr) return;
	    p=p->next;
	}
    ListNode* deleteNode=p->next;
    p->next=deleteNode->next;
    delete deleteNode;
    deleteNode=nullptr;
}

四、经典题目

206.反转链表

只需要改变链表的next指针的指向，直接将链表反转。

1. 定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null
2. 把 cur->next 节点用next指针保存一下，反转cur，pre和cur后移
3. 重复第二步直到cur 指针指向了null，return pre即可

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur=head;
        ListNode* pre=NULL;
        ListNode* next;
        while(cur!=nullptr){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

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

双指针的经典应用，并且可以使用虚拟头结点方便处理删除实际头结点的逻辑。

1. 创建一个虚拟头结点，fast和slow都指向虚拟结点
2. fast移动n步
3. slow和fast一起后移，直到fast->next为空
4. slow->next就是要删除的结点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast=new ListNode(0);
        ListNode* slow;
        fast->next=head;
        head=fast;
        slow=head;
        while(n--) fast=fast->next;
        while(fast->next!=nullptr){
            slow=slow->next;
            fast=fast->next;
        }
        ListNode* tmp=slow->next;
        slow->next=slow->next->next;
        delete tmp;
        tmp=nullptr;
        return head->next;
    }
};

面试题02.07.链表相交

类似不倍增的lca做法。

求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int sizeA=0,sizeB=0;
        ListNode *p=headA;
        while(p!=nullptr) {
            p=p->next;
            sizeA++;
        }
        p=headB;
        while(p!=nullptr) {
            p=p->next;
            sizeB++;
        }
        ListNode *q;
        if(sizeA>sizeB){
            int n=sizeA-sizeB;
            p=headA;
            while(n--) p=p->next;
            q=headB;
        }
        else{
            int n=sizeB-sizeA;
            p=headB;
            while(n--) p=p->next;
            q=headA;
        }
        ListNode *ans=NULL;
        while(p!=nullptr && q!=nullptr){
            if(p==q){
                ans=p;
                break;
            }
            p=p->next;
            q=q->next;
        }
        return ans;
    }
};

142.环形链表II

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

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

那么相遇时： slow指针走过的节点数为 x+y，fast指针走过的节点数为x+y+n*(y+z)。

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以fast指针走过的节点数=slow指针走过的节点数乘2。

$$\begin{aligned} 2\times(x+y)&=x+y+n\times(y+z)\\ x&=z+(n-1)\times(y+z)\\ \end{aligned}$$

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

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head==NULL || head->next==NULL) return NULL;
        ListNode *fast=head->next->next;
        ListNode *slow=head->next;
        while(fast!=slow){
            if(fast==NULL || fast->next==NULL) return NULL;
            fast=fast->next->next;
            slow=slow->next;
        }
        slow=head;
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};

五、其他相关题目

• 203.移除链表元素
• 24.两两交换链表中的结点