概念：

  • 类别： 链表是一种线性表，但它是非连续的,概念上连续，空间上不连续。
  • 时间复杂度：查找为O(n)，插入删除为O(1)，比数组查找麻烦，增删简单。
  • 分类： 单向链表，双向链表，单向循环链表，双向循环链表。
  • 实现方法： 通常我们用结构体来封装链表里面的每个节点，里面通常包含数据域和指针域。数据域里面存放每个节点的数据，指针域里面存放该节点的上一个节点或者下一个节点。
  • 说明： 本节练习基本均来自牛客130系列，链接：两两交换链表中的结点_牛客题霸_牛客网

代码实现：

链表的声明：

一、单向链表：

概念：单向链表的指针域里面只存放了他的下一个节点，只有一个指针域，只能单向移动，不能回溯，一旦过去就找不到上一个元素了
代码实现：

1
2
3
4
5
6
struct ListNode{
4int num;  //数据域
4ListNode* next; //定义一个指向ListNode的指针，也就是指针域
4ListNode(int x):num(x),next(nullptr){} //构造函数，初始默认指针指向空指针，x直接赋值给num。
4//适合搭配new，来给新节点赋值。
};

二、双向链表：

概念： 字面意思，就是可以往两边遍历，有两个指针域。
代码实现：

1
2
3
4
5
6
struct ListNode{
4int num;
4ListNode* next; //指向下一个指针
4ListNode* pre; //指向上一个指针
4ListNode(int x,ListNode* p):num(x),next(nullptr),pre(p){} //给pre赋值，使得其知道从哪里来的。
};

三、循环链表：

概念： 循环链表的声明相同，主要不同点是，循环链表的尾节点的指针域不指向空指针，而是指向头结点，双向循环链表的头节点pre指向尾节点。

常见操作：

序列链表化：

  • 将数组或序列转化为链表，或者链表的定义。
    代码实现：
1
2
3
4
5
6
7
8
9
10
11
ListNode* vectorToListnode(vector<int>& arr) {
        ListNode* head=new ListNode(0); //定义头节点
        ListNode* p=head; //定义遍历的指针，初始指向头结点
        for(auto i:arr){ //遍历arr容器
            p->next=new ListNode(i);  //new返回新ListNode的指针并赋值给p->next;
            p=p->next; //指针移动,给下一个元素操作
        }
        ListNode* newhead=head->next; //head的下一个节点存的是我们的第一个元素
        delete head;  //释放head的内存
        return newhead;  //返回链表的头结点。
    }
  • 链表序列化的操作与此类似，就不多演示了。

链表删除操作：

  • 思路： 假如我们要删除某个节点，那么我们将这个节点的上一个节点的指针域指向下一个节点的，就将中间这个节点跳过了，之后将其内存再释放就完成了节点的删除。
    代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode* removeElements(ListNode* head, int val) {
        //创造虚拟头结点，链表里面对头结点和尾节点极其重要，一旦访问空指针就会直接报错(段错误)
        ListNode* tem=new ListNode(0);
        tem->next=head; //真实头结点
        ListNode* p=tem; 
        while(p->next!=nullptr){ //遍历链表
            if(p->next->val==val){ //检查p的下一个节点是不是目标值
                ListNode* todelete=p->next; //记录待删除节点的指针
                p->next=p->next->next; //跳过中间值
                delete todelete; //释放内存
            }
            else p=p->next; //不符合就跳到下一个节点
        }
        ListNode* newhead=tem->next; //虚拟头结点的下一个节点就是我们需要的头结点
        delete tem; //删除虚拟头结点
        return newhead;
    }

反转链表：

  • 思路： 我们为了高效期间，不用先序列化再链表化的方式，而是直接一次运行完。
  • 流程：
    1. 我们要干的操作就是将后一个元素的指针指向前一个元素，但我们改变指针后，就没法往后遍历了，后面的节点就丢失了。
    2. 因此，我们定义两个指针，一前一后的往后遍历，一个指针来保存当前遍历到的指针，另一个指针来指引前一个节点的地址，同时还要有个临时指针来存下一个节点的位置。
    3. 之后将后面的指针更新到当前指针的位置，将当前的移动到临时指针的位置，就完成了不断更新的操作。
      代码实现：
1
2
3
4
5
6
7
8
9
10
11
ListNode* ReverseList(ListNode* head) {
        //定义两个变量来指引我们遍历的节点。
        ListNode* cur=head,*pre=nullptr;
        while(cur!=nullptr){
            ListNode* tem=cur->next;//反转链表要保存下一个节点的信息
            cur->next=pre; //将当前节点的next更新为前一个节点
            pre=cur; //更新两个指针
            cur=tem;
        }
        return pre;
    }

判断链表是否是回文结构：

  • 思路： 对于回文结构的判断，一般如果是连续表，可以用双指针来从两边到中间来判断，如果是双向链表也可以这样判断，对于单向链表我们可以用快慢指针+反转链表来判断。
  • 快慢指针原理： 我们定义两个指针来遍历链表，分别为fast和slow，快指针每次移动两个节点，慢指针每次移动一个节点，我们的条件判断是快指针的下一个节点，和下下个节点都存在，再进行移动，共分为两种情况。
    1. 如果链表节点数位奇数，那么假如有5个节点，刚开始都在第一个节点，一次判断后，fast 移动到3，slow 移动到2，第二次判断后，fast 移动到5，slow 移动到3，之后条件判断失败，停止，slow 的下一位就是我们要反转的头结点。
    2. 如果链表节点为偶数，假如有6个节点，第一次后fast=3 ,slow=2,第二次后fast=5,slow=3 ，第三次判断，条件判断失败，停止循环，可以看到，slow 为3，其下一位就是我们要反转字符串的头节点。
  • 总结： 可见无论奇偶，最后我们慢指针的下一位就是我们要反转的头结点，之后从slow的下一位开始反转，，反转完之后的问题就简单了。
    代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
    ListNode* reverseList(ListNode* head){ //反转链表的函数
        ListNode* cur=head;
        ListNode* pre=nullptr;
        while(cur!=nullptr){
            ListNode* tem=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tem;
        }
        ListNode* newhead=pre;
        return newhead;  //返回的这个反转链表其实和之前的链表已经完全切割了，中间没有东西相连，这个反转链表最后指向的为空指针。
    }
    bool isPail(ListNode* head) {
        ListNode* fast=head,*slow=head; //定义快慢指针，
        while(fast->next&&fast->next->next){ //指向nullptr的指针等效于false，
            fast=fast->next->next; //快慢指针的移动
            slow=slow->next;
        }
        ListNode* newhead=reverseList(slow->next);
        bool judge=true;
        while(newhead){ //这里新的反转链表长度<=原链表的一半。
            if(newhead->val!=head->val){
                judge=false; //判断是否相等。
                break;
            }
            newhead=newhead->next; //移动指针
            head=head->next;
        }
        return judge; //返回结果
    }

思维题：

来源： 来自牛客130
题目一： 链接：链表相交_牛客题霸_牛客网
题目二： 链接：插队_牛客题霸_牛客网
这两道题的题的题解可以参考题目旁边的题解里面的大神思路，也可以看我GitHub上的题解
GitHub题解链接：链表题解