算法与数据结构学习笔记：链表

核心知识点

null异常处理
dummy node 哑巴节点
双指针/快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点

例题：

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3

直接法：

链表是有序的，所以直接更改当前结点的 next 指针，跳过下一个结点并直接指向下一个结点之后的结点即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *current=head;
        //null异常处理
        while(current!=NULL&&current->next!=NULL)
        {
            //一直删除，直到下一个不重复 
            // 想想如果把while改成if怎么样
            //把current->next!=NULL删除会怎么样
            while(current->next!=NULL&&current->val==current->next->val)
            {
                current->next=current->next->next;
            }
            //移动到下一个节点
            current=current->next;
        }
        return head;


    }
};

时间复杂度：O(n)，因为列表中的每个结点都检查一次以确定它是否重复，所以总运行时间为 O(n)，其中 n是列表中的结点数。
空间复杂度：O(1)，没有使用额外的空间。

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3

利用哑结点：

为了防止删除头结点的极端情况发生，先创建空结点dummy，使dummy指向传入的head结点。

然后创建一个cur指针指向dummy，比较cur的后两个结点，看他们是否相同。

如果相同，则说明cur后有重复元素，此时创建一个temp指针指向第一个重复元素，即cur->next;

通过循环进行去重，循环结束后temp指向的是这群重复元素的最后一个，依照题意此时temp的下一个才是我们想要的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //设置哑结点 防止删除头结点的情况发生后的问题
        ListNode *dummy=new ListNode(-1);
        dummy->next=head;
        ListNode *cur=dummy;//cur 指向哑结点

        while(cur->next!=NULL&&cur->next->next!=NULL)
        {
            //比较cur后两个结点
            if(cur->next->val==cur->next->next->val)
            {
                //去重
                ListNode *temp=cur->next;
                while(temp->next!=NULL&&temp->val==temp->next->val)
                {
                    temp=temp->next;
                }
                //temp前的重复结点都跳过了，现在我们跳过temp
                cur->next=temp->next;
            }
            else
            {
                //如果cur后两个结点不重复，直接前移
                cur=cur->next;
            }
        }
        return dummy->next;
    }
};

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

206. 反转链表

反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

双指针

如图，定义两个指针，pre在前 cur在后,temp 保存向前的pre指针的临时指针

每次进行一次局部翻转，

当pre到达尾部的时候终止，此时cur指向最后一个节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        /*定义两个指针，pre在前 cur在后
         *当pre到达尾部的时候终止，此时cur指向最后一个节点
         */
        ListNode *pre=head;
        ListNode *cur=NULL;
        ListNode *temp=NULL;
        while(pre!=NULL)
        {
            temp=pre;//临时存储pre
            pre=pre->next;//pre指向下一个节点
            temp->next=cur;//翻转指针
            cur=temp;//cur指针向前移动一步
        }
        return cur;

    }
};

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
>输入: 1->2->3->4->5->NULL, m = 2, n = 4
>输出: 1->4->3->2->5->NULL

迭代法：

参考上题，先遍历到 m 处，再翻转

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(head==NULL)
            return NULL;

        ListNode *pre,*cur;
        pre=head;
        cur=NULL;
        
		//遍历到m节点，如果只有一个节点，跳过，这里cur会为空但是后面翻转链表的时候就不是了
        while(m>1)
        {
            cur=pre;
            pre=pre->next;
            m--;
            n--;
            
        }

		//m节点的前一个节点
        ListNode*con=cur;
        ListNode*temp=NULL;
        //用于保存被翻转链表的第一个节点
        ListNode*front=pre;
        
      
        
		//反转m-n的节点
        while(n--)
        {
            temp=pre;
            pre=pre->next;
            temp->next=cur;
            cur=temp;
        }
        
		//如果不只是一个节点，那么就把指针指向被翻转的链表的最后一个节点
        if(con!=NULL)
        {
            con->next=cur;
        }
        else
        {
            //否则直接输出此节点
            head=cur;
        }
        //被翻转的链表原来的头变尾
        front->next=pre;
        return head;
    }
};

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

迭代法：

直接连接各个节点

/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {

        ListNode *dummy=new ListNode(-1);
        ListNode *cur=dummy;
        //将小的节点接到哑结点为头的链表中
        while(l1!=NULL&&l2!=NULL)
        {
            if(l1->val>l2->val)
            {
               cur->next=l2;
               cur=cur->next;
               l2=l2->next;
            }
            else
            {
                cur->next=l1;
                cur=cur->next;
                l1=l1->next;
            }

        }
        
        //处理剩下的节点
        if(l1!=NULL)
        {
            cur->next=l1;
        }
        if(l2!=NULL)
        {
            cur->next=l2;
        }
        return dummy->next;

    }
};

86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

当头节点不确定的时候，使用哑巴节点

将大于 x 的节点，放到另外一个链表，最后连接这两个链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head==NULL)
            return head;
        ListNode *headDummy=new ListNode(-1);
        ListNode *tailDummy=new ListNode(-1);
        ListNode *cur=NULL,*tail=tailDummy;
        headDummy->next=head;
        
        head=headDummy;
		
        while(head->next!=NULL)
        {
            if(head->next->val<x)
            {
                head=head->next;
            }
            //这里把大于X的节点删除，然后连接到另一个链表
            else
            {
                cur=head->next;
                //删除大于X的节点
                head->next=head->next->next;
                //连接到新链表
                tail->next=cur;
                tail=tail->next;


            }
        }
        //拼接两个链表
        //tail代表tailDummy最后一个节点，它的后面可能还连着，要断掉
        //如输入[1,4,3,2,5,2]就会有错,没有处理5->2
        tail->next=NULL;
        
        head->next=tailDummy->next;
        return headDummy->next;

        
    }
};

876. 链表的中间结点

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

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

    }
};

总结：如果链表长度是偶数，返回中间偏右的位置

且fast如果初始化为head->next 返回中间偏左的位置。

奇数长度则两者相同。

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5

递归

归并排序链表，找中点和合并操作

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return mergeSort(head);

    }
    //寻找链表中点，快慢指针，快的到达终点，慢的刚好到中点 
    //当链表的长度是奇数时，slow 恰巧停在中点位置；如果长度是偶数，slow 最终的位置是中间偏右：
    //此题我们让head先走，则停在中间偏左的位置
    //148 143 141都有快慢指针
    ListNode *findMiddle(ListNode *head)
    {
        ListNode *slow,*fast;
        slow=head;
        fast=head->next;
        while(fast!=NULL&&fast->next!=NULL)

        {
            slow=slow->next;
            fast=fast->next->next;

        }
        return slow;
    }
    //合并两个链表，参考归并排序
    ListNode * mergeTwoLists(ListNode*left,ListNode*right)
    {
        ListNode *dummy=new ListNode(-1);
        ListNode *head=dummy;
        while(left!=NULL&&right!=NULL)
        {
            if(left->val>right->val)
            {
                head->next=right;
                right=right->next;
            }
            else
            {
                head->next=left;
                left=left->next;
            }   
            //下一个
            head=head->next;
        }
        //处理剩下节点
        while(left!=NULL)
            {
                head->next=left;
                head=head->next;
                left=left->next;
            }
            while(right!=NULL)
            {
                head->next=right;
                head=head->next;
                right=right->next;
            }
        return dummy->next;
    }
	
    ListNode *mergeSort(ListNode *head)
    {
        if(head==NULL||head->next==NULL)
        {
            return head;
        }

        ListNode *middle=findMiddle(head);

        // 断开中间节点
        ListNode* tail=middle->next;
        middle->next=NULL;
        //左右分别进行归并排序
        ListNode *left=mergeSort(head);
        ListNode *right=mergeSort(tail);
        ListNode *res=mergeTwoLists(left, right);
        return res;
    }
};

143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

此题目为2019年计算机统考408真题

思路：找到中点断开，翻转后面部分，然后合并前后两个链表

/**
 * 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:
    
    //快慢指针找中点，同上一题 
    //148 143 141都有快慢指针
    ListNode * findMiddle(ListNode *head)
    {
        ListNode *slow,*fast;
        slow=head;
        fast=head;
        //如果是偶数个节点，返回中间偏右的位置 
        //你改成fast=head->next返回中间偏左也是对的
        //有趣吧，画个图就知道了
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;

    }
    
    //合并两个链表
    ListNode * mergeTwoLists(ListNode* l1,ListNode*l2)
    {
        ListNode* dummy=new ListNode(-1);
        bool  toggle =true;
        ListNode *head=dummy;
        //间断连接两个链表
        while(l1!=NULL&&l2!=NULL)
        {
            if(toggle)
            {
                head->next=l1;
                l1=l1->next;
            }
            else
            {
                head->next=l2;
                l2=l2->next;
            }
            toggle=!toggle;
            head=head->next;
        }
        //连接剩下的节点
        while(l1!=NULL)
        {
            head->next=l1;
            l1=l1->next;
            head=head->next;

        }
        while(l2!=NULL)
        {
            head->next=l2;
            l2=l2->next;
            head=head->next;

        }
        return dummy->next;
    }
    
    void reorderList(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return ;
        
        //找到中点 断开
        ListNode *middle=findMiddle(head);
        ListNode *tail=middle->next;
        middle->next=NULL;
        //翻转链表
        ListNode *cur,*pre;
        pre=tail;
        cur=NULL;
        while(pre!=NULL)
        {
            ListNode *temp=pre;
            pre=pre->next;
            temp->next=cur;
            cur=temp;
        }
        tail=cur;
        
        //合并链表
        head->next=mergeTwoLists(head,tail)->next;                
    }
    
};

141. 环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

快慢指针即可，就像你在操场跑步，操场有环，只要你和她速度不一样，你们总能与她相遇，如果是直线，她到了终点，你就再也追不上她

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//148 143 141 142都有快慢指针
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL)
            return false;
        ListNode *fast,*slow;
        slow=head;
        fast=head;
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
            // 比较指针是否相等
            if(slow==fast)
                return true;
        }
        
        return false;
    }
};

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

。

Floyd 算法

你在操场跑步，操场有环，只要你和她速度不一样，你们总能与她相遇，如果是直线，她到了终点，你就再也追不上她。此题分为两个阶段，第一个阶段先用快慢指针测试是否有环，第二阶段慢指针回到头head,然后各自以相同速度前进，相遇点即为入环处（可以自己画图尝试）。严格的数学证明可参考leetcode官方题解。

/**
 * 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) {
        if(head==NULL)
            return NULL;
        ListNode *slow,*fast;
        slow=head;
        fast=head;//如果这里是fast=fast->next，那么下面该怎么改？
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                //回到起点，各自以相同速度前进
                slow=head;
                while(slow!=fast)
                {
                    slow=slow->next;
                    fast=fast->next;

                }
                return slow;
            }                        
        }     
        return NULL;
    }
};

234. 回文链表

请判断一个链表是否为回文链表。
示例 1:
>输入: 1->2
>输出: false
示例 2:
>输入: 1->2->2->1
>输出: true

先找到链表中点，然后后面的翻转链表，一个个比较。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL)
            return true;
        ListNode *slow,*fast;
        slow=head;
        fast=head->next;
        while(fast!=NULL&&fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        //偶数长度slow是中间偏左的节点
        //奇数长度slow是中点

        ListNode *cur,*pre,*tail,*temp;
		//分离两个链表
        tail=slow->next;
        slow->next=NULL;
		//翻转链表
        pre=tail;
        cur=NULL;
        while(pre!=NULL)
        {
            temp=pre;
            pre=pre->next;
            temp->next=cur;
            cur=temp;
        }
        //原链表的最后一个节点现在变成头结点
        tail=cur;

        while(head!=NULL&&tail!=NULL)
        {
            if(tail->val!=head->val)
            {
                return false;
            }
            head=head->next;
            tail=tail->next;

        }
        return true;

    }
};

138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

复制节点跟在原节点后面即可

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==NULL)
            return head;
        auto cur=head;
        //复制节点到后面
        while(cur!=NULL)
        {
            auto clone=new Node(cur->val);
            clone->next=cur->next;
            clone->random=cur->random;
            cur->next=clone;
            cur=clone->next;
        }
         //处理random指针
        cur=head;
        while(cur!=NULL)
        {
            if(cur->random!=NULL)
            {
                cur->next->random=cur->random->next;
            }
            cur=cur->next->next;
        }
        //分离链表
        cur=head;
        auto cloneHead=cur->next;
        while(cur!=NULL&&cur->next!=NULL)
        {
            auto temp=cur->next;
            cur->next=cur->next->next;
            cur=temp;
            
        }
        return cloneHead;
    }
};

核心知识点

例题：

直接法：

利用哑结点 ：

双指针

迭代法：

迭代法：

递归

Floyd 算法

利用哑结点：