【链表】数据结构与算法——代码随想录

学习目的
1.会链表的定义、常用的基本操作。
2.会解决几种常用的链表相关的题目。

（一）链表基础知识
1.概念基础
（1）组成：数据+指针
（2）类型：单链表、双链表、循环链表
（3）存储方式：分散存储
2.代码实现
（1）节点定义

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

（2）节点初始化
初始化节点：
使用默认构造函数初始化节点时，默认构造函数不会初始化头结点。

ListNode*head = new ListNode()
head->val = 5;

（3）虚拟头结点

//设置一个虚拟的头结点
ListNode* dummyHead = new ListNode(0);
//让头结点与head发生联系
dummyHead->next = head;
//定义一个新的节点，对现有链表进行操作
ListNode* cur = dummyHead;
...//之间是删除添加等一些基本操作
//把头结点还给头结点
head = dummyHead->next;
//删除虚拟结点
delete dummyHead;
return head;

3.常用操作
（1）删除结点
（2）添加结点

（二）链表例题
1.移除链表中的元素
移除链表中的元素
题目梳理：删除满足某一个值的所有结点
步骤：
a.设置虚拟头结点（考察结点的创建，初始值以及下一个指针的指向）【在代码的末端同步写一个删除头结点】
b.遍历列表（链表中结点具体值的读取、while 循环的编写）
c.删除符合条件的结点（链表结点的删除）
运行时出现的错误以及解决：LeetCode：执行出错runtime error: member access within null pointer of type ‘ListNode‘ (solution.cpp)解决方法

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while (cur!=NULL&&cur->next != NULL){//需要有一个这样的判断条件通常
            if(cur->next->val == val){
                ListNode* tempt = cur->next;
                cur->next=cur->next->next;
                delete tempt;
            }else{
                cur = cur->next;
            }
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

总结：写if时需要把条件满足时执行的语句和条件不满足执行的语句都写清楚
2.翻转链表
翻转链表
反转一个单链表
步骤：
因为反转过程中需要把链表变成两节，所以需要两个指针才能反转链表。
a.定义两个指针指向链表的前两个节点
b.按顺序依次更改链表指针的方向（cur要从头结点开始，pre先定义为空指针，属于对边界条件的考虑不够准确）
c.循环结束的标志是链表末尾的空指针

//双指针法，递归法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;//注意边界条件，一开始把pre初始化为头结点，导致反转后的链表没有尾巴的空指针
        ListNode* tempt1; //临时存储前一个结点的指向
        ListNode* pre = NULL;//注意初始化
        while(cur){
            tempt1 = cur->next;//为了不丢失后一个节点的信息
            cur->next = pre;//将cur结点调整了指向位置
            pre = cur;//把当前结点变成过去式
            cur=tempt1;//对下一个结点进行操作
        }
        return pre;//注意事return pre，return cur就会指向空处，不是一个正确的链表头
    }
};

class Solution {
public:
    ListNode* reverse(ListNode*pre,ListNode*cur){//递归第一步，确认输入变量
        if(cur==NULL) return pre;//递归的终止条件
        //不满足终止条件的交换指向
        ListNode* tempt;//交换问题一般都会有一个中间装载容器
        tempt = cur->next;//交换指针指向
        cur->next = pre;
        return reverse(cur,tempt);//单层递归逻辑

    }
    ListNode* reverseList(ListNode* head) {
        return reverse(NULL,head);
    }
};

3.两两交换链表中的节点
两两交换链表中的节点
借助第三个结点来完成结点的两两交换，多个指针的交换顺序非常重要。
步骤：
a.定义一个虚拟的头接点，最后记得删除头结点
b.定义两个临时节点，保证两个元素，和后部分的元素的头结点
c.两个元素之间进行的是类似反转链表的操作
d.遍历整个链表，用一个指针每一步走两个节点
报错出现超出时间限制时注意去找循环的问题
指针使用关键，用之前先进行存储。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode*cur = dummyHead;

        while(cur->next!=NULL&&cur->next->next!=NULL){
            ListNode* tempt1;
            tempt1 = cur->next;//为了防止头结点丢失，所以在交换时一定要注意存储头结点这操作,存起来就对这个指针指向进行操作
            cur->next = cur->next->next;
            ListNode* tempt2;
            tempt2 = cur->next->next;
            cur->next->next = tempt1;
            tempt1->next = tempt2;
            cur = cur->next->next;
        }
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

4.删除链表的倒数第N个点
删除链表的倒数第N个点
链表的最末尾是空指针，用此来判断满指针此时指向的是倒数N个。
删除元素+倒数第N个点的定位
步骤：
a.定义一个头结点定义,fast和slow两个指针
b.先将fast指针移动n+1步
c.同时移动快指针和慢指针，知道快指针到了末尾
此时慢指针指向的下一个结点就是待删除的元素。
d.删除元素的操作。

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--){//让快指针先走N+1步,果然要自己亲自画才能体会到N+1步的妙处，删除结点指向的下一个元素是相对容易的。
            fast = fast->next;
        }
        fast = fast->next;
        while(fast!=NULL){//两个指针一直向后移动
            slow = slow->next;
            fast = fast->next;
        }
        //删除此时slow->next指针所指元素
        ListNode*tempt;
        tempt = slow->next;
        slow->next = tempt->next;
        delete tempt;
        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};

5.返回两个链表相交的起始点
相交结点不是用数值相等判断而是用指针相同进行判断。
步骤：
a.求出两个链表的长度，求出两个链表长度的差值
b.让curA移动到和curB末尾对其的的位置
两个链表相交后后面的链表是共用的。
c.比较curA和curB是否相同
相同返回交点，
不相同则返回空指针。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //定义可以操作的链表头是常用的处理方式
        ListNode* curA = headA;
        ListNode* curB = headB;
        //定义链表长度
        int lenthA = 0;
        int lenthB = 0;
        //求出每个链表的长度,没有专门的计算长度的函数，所以用遍历循环的方法进行计数
        while(curA!=NULL){
            lenthA++;
            curA=curA->next;
        }
        while(curB!=NULL){
            lenthB++;
            curB=curB->next;
        }
        //此时curA和curB的指向发生了变化，需要重新调整回去
        curA = headA;
        curB = headB;
        //对A,B链表的长度进行处理
        if(lenthB>lenthA){
            swap(lenthA,lenthB);
            swap(curA,curB);
        }
        int gap = lenthA-lenthB;
        while(gap--){
            curA = curA->next;
        }
        while(curA!=NULL){
            if(curA==curB){
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;    
    }
};

6.环形链表
判断链表中是否有环，环的入口；
环形链表的应用：解决约瑟夫环问题
已知 n 个人（以编号 1，2，3，…，n 分别表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，要求找到最后出列的那个人。

环的入口，需要画图理解相关的数学知识
步骤：
a.定义快慢指针
b.快慢指针如果相遇，则链表中存在环
在相遇的位置定义一个新指针1，再在头结点处定义一个新指针2，
两个指针相遇的位置一定是在环的入口处,可以从公式的角度理解这一层关系。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //定义两个指针
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow){
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1!=index2){//这里的条件判断不能用if...else...,它只执行一次，while则会一直循环
                    index1 = index1->next;
                    index2 = index2->next;                    
                }
                return index2;
            }
        }
        return NULL;    
    }
};

7.删除链表中有序链表中的重复元素
删除链表中有序链表中的重复元素
解题思路：有点像双指针

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy=new ListNode(-1);
        ListNode* slow=dummy,* fast=head;
        dummy->next=head;

        while(fast && fast->next)
        {
        //通过fast找到不再重复的结点
            if(fast->val!=fast->next->val)
            {
            //如果fast是重复的结点
                if(slow->next!=fast) slow->next=fast->next;
                else slow=fast;
            }
            fast=fast->next;
        }
        //在链表结尾的处理
        if(slow->next!=fast) slow->next=fast->next;
        return dummy->next;
    }
};