[数据结构与算法]【Leetcode】链表 简单题大全 c++

主要使用的方法：

快慢指针；new ListNode()构造新节点；

1.【移除重复节点】

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

示例2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]

提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

【方法1 哈希 c++代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if(head==nullptr)return head;
        map<int,int> m;
        ListNode* node = new ListNode(-1,head);
        ListNode* temp = node;
        while(head!=nullptr){
            int val = head->val;
            if(m[val]==0){
                m[val]+=1;
                temp->next=head;
                temp=temp->next;
                head=head->next;
            }
            else{ //删除当前节点head
                head=head->next;
                if(head==nullptr){
                    temp->next=nullptr;
                }
            }
        }
        return node->next;
    }
};

【方法2 双重循环 c++代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        if(head==nullptr)return head;
        ListNode* node = head;
        while(node!=nullptr){
            ListNode* node2 = node;
            while(node2->next!=nullptr){
                if(node->val==node2->next->val){ 
                    node2->next = node2->next->next;//下一个是下下一个
                }
                else{
                    node2 = node2->next;//变成下一个
                }
            }
            node=node->next;
        }
        return head;
    }
};

2.【返回倒数第k个节点】

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：

输入： 1->2->3->4->5 和 k = 2
输出： 4

说明：

给定的 k 保证是有效的。

【c++代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        int n=0,s=0;
        ListNode* node = head;
        while(node!=nullptr){
            s+=1;
            node = node->next;
        }
        if(k>s)return -1;
        while(head!=nullptr){
            n+=1;
            if(n==(s-k+1))return head->val;
            head = head->next;
        }
        return -1;
    }
};

【双指针法 c++代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* fast = head;
        ListNode* slow = head;
        int s=0;
        while(k!=0){ //fast比slow多走k个，slow在0，fast在k
            if(fast==nullptr)return -1;
            fast = fast->next;
            k--;
        }
        while(fast!=nullptr){ //fast比slow多走k个，如果fast到达终点，slow停止则slow比fast少走k个，fast到达nullptr，slow到达倒数第k个
            fast = fast->next;
            slow = slow->next;
        }
        return slow->val;
    }
};

（1）初始化双指针 pre , cur 都指向头节点 head ；
（2）先令 cur 走 kk 步，此时 pre , cur 的距离为 kk ；
（3）令 pre , cur 一起走，直到 cur 走过尾节点时跳出，此时 pre 指向「倒数第 kk 个节点」，返回之即可；

3.【删除中间节点】

若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。

假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。

例如，传入节点 c（位于单向链表 a->b->c->d->e->f 中），将其删除后，剩余链表为 a->b->d->e->f

示例：

输入：节点 5 （位于单向链表 4->5->1->9 中）
输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9

【c++代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val; //当前节点赋值为下一节点的值
        node->next = node->next->next; //当前节点的下一节点为下下一个节点
    }
};

直接修改当前节点的值，并把指针指向下下一个节点即可，不需要用到前缀节点。

4.【回文链表】

编写一个函数，检查输入的链表是否是回文的。

示例 1：

输入： 1->2
输出： false

示例 2：

输入： 1->2->2->1
输出： true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

【c++代码】

/**
 * 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) {
        vector<int> v;
        int sum=0;
        while(head!=nullptr){
            v.push_back(head->val);
            sum+=1;
            head=head->next;
        }
        for(int i=0;i<sum;i++){
            if(v[i]!=v[sum-1-i])return false;
        }
        return true;
    }
};

【进阶 快慢指针+反转链表 c++代码】

/**
 * 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==nullptr)return true;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast!=nullptr&&fast->next!=nullptr){//双指针，slow到达中间节点or第二个中间节点
            fast = fast->next->next; 
            slow = slow->next; 
        }
        ListNode* node; //后半段链表的起始节点
        if(fast==nullptr){//链表长度为偶数
            node = slow;
        }
        else{ //奇数
            node = slow->next;
        }
        //后半段反转
        ListNode* temp = node;
        ListNode* pre = nullptr;
        int s=0;
        while(temp!=nullptr){
            ListNode* nextnode = temp->next; //记录下一个要改变的节点
            temp->next = pre; //改其指向前一个节点
            s+=1;
            pre = temp; //更新前一个节点为当前节点
            temp = nextnode; //更新当前节点为下一节点
        }
        //与前半段做比较
        int a=0;
        while(s>0){
            if(pre->val==head->val){
                s-=1;
                pre = pre->next;
                head = head->next;
            }
            else return false;
        }
        return true;
    }
};

为了不使用多余的空间，需要使用快慢指针把链表分为前后两部分，再反转链表，比较前后两个链表的值是否相等。

4.【链表相交】

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at ‘2’
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

【进阶 双指针 c++代码】

/**
 * 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) {
        if(headA==nullptr||headB==nullptr)return nullptr;
        ListNode* hA=headA;
        ListNode* hB=headB;
        while(hA!=hB){//没相遇之前
            if(hA==nullptr)hA=headB;
            else hA = hA->next;
            if(hB==nullptr)hB=headA;
            else hB = hB->next;
        }
        if(hA==nullptr)return nullptr;
        else return hA;
    }
};

5.【BinNode 把二叉搜索树变成单链表】

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

注意：本题相对原题稍作改动

示例：

输入： [4,2,5,1,3,null,6,0]
输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]

提示：
节点数量不会超过 100000。

【递归 c++代码】

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *ans = new TreeNode(0),*cur=ans;
    void inOrder(TreeNode* node)
    {
        if(node==NULL)  return ;
        inOrder(node->left);
        node->left=NULL;    //将该节点的左孩子设为NULL
        cur->right=node;    //将该节点赋给上一个节点的右孩子
        cur=node;           //更新cur
        inOrder(node->right);
    }
    TreeNode* convertBiNode(TreeNode* root) {
        inOrder(root);
        return ans->right;
    }
};

6.【合并两个有序链表】

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

【c++代码】

/**
 * 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* list1, ListNode* list2) {
        ListNode* head = new ListNode(-1);
        ListNode* node = head;
        while(list1!=nullptr&&list2!=nullptr){
            if(list1->val<=list2->val){
                head->next = list1;
                list1 = list1->next;
            }
            else{
                head->next = list2;
                list2 = list2->next;
            }
            head = head->next;
        }
        if(list1!=nullptr)head->next=list1; //可能list1有剩余或list2有剩余，直接加在head后面
        if(list2!=nullptr)head->next=list2;
        return node->next; 
    }
};

7.【删除排序链表中的重复元素】

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列

【c++代码】

/**
 * 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* deleteDuplicates(ListNode* head) {
        ListNode* node = new ListNode(-1);
        ListNode* n = node;
        int pre = -101;
        while(head!=nullptr){
            int val = head->val;
            if(val!=pre){
                node->next = new ListNode(val);
                node = node->next;
                pre = val;
            }
            head=head->next;
        }
        return n->next;
    }
};

8.【环形链表】

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例1：

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

示例2：

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

示例3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

【c++代码】

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr)return false;
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast!=slow){
            if(fast==nullptr||fast->next==nullptr)return false;//fast在没有相遇之前先到达了尾部，没有环（没有回头）
            fast = fast->next->next;
            slow = slow->next;
        }
        return true;
    }
};

判断是否有环：

fast=head->next，slow=head，fast一次两步，slow一次一步

如果fast在没与slow相遇之前就到达nullptr(尾部)，说明fast没有回头，链表无环。

9.【移除链表元素】

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

【c++代码】

/**
 * 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* node = new ListNode(-1);
        ListNode* h = node;
        while(head!=nullptr){
            if(head->val!=val){
                node->next = new ListNode(head->val);
                node = node->next;
            }
            head=head->next;
        }
        return h->next;
    }
};

10.【反转链表】

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

【c++代码】

/**
 * 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==nullptr)return nullptr;
        ListNode* pre = nullptr;
        while(head!=nullptr){
            ListNode* nextnode = head->next;
            head->next = pre;
            pre = head;
            head = nextnode;
        }
        return pre;
    }
};

11.【链表的中间节点】

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

【快慢指针 c++代码】

/**
 * 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* middleNode(ListNode* head) {
        if(head==nullptr)return nullptr;
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast!=nullptr&&fast->next!=nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow; //慢指针在中间几点或偶数的中间第二节点处
    }
};

12.【二进制链表转整数】

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

【c++代码】

/**
 * 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:
    int getDecimalValue(ListNode* head) {
        if(head==nullptr)return 0;
        string s="";
        while(head!=nullptr){
            char ch = head->val+'0';
            s+=ch;
            head=head->next;
        }
        int res = stoi(s,0,2);
        return res;
    }
};

使用函数stoi(s,a,b)：把b进制的字符串s，从第a位开始转化，返回转化为的10进制整数。