• 算法--单链表

    算法–单链表

    1.合并链表

    1.合并两个排序的链表

    • 解法：这个比较容易，直接对比两个两个链表节点，小的节点直接插入到返回的新链表上

      /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* dummy = new ListNode(0);
        ListNode* p = dummy;

        if(pHead1 ==nullptr){
            return pHead2;
        }
        if(pHead2 == nullptr){
            return pHead1;
        }

        while (pHead1 && pHead2) {
            if(pHead1->val > pHead2->val){
                p->next = pHead2;
                p = p->next;
                pHead2= pHead2->next;
            }
            else {
                p->next = pHead1;
                p= p->next;
                pHead1= pHead1->next;
            }
        }

        if(pHead1 ==nullptr){
            p->next = pHead2;
        }
        if(pHead2==nullptr){
            p->next = pHead1;
        }

        return dummy->next;
    }
};

      • 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
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48
      • 49
      • 50
      • 51

    2.合并K个有序链表

    • 解法：这个稍微复杂一些，需要找到k个链表中节点的最小值。所以我们需要借助优先队列（小根堆），先获取每个链表的第一个节点的大小关系，然后获取当前最小节点链表的后续节点加入到队列。依赖优先队列的自动排序的特性，很容易获得从小到大的链表。

      /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include 
#include 
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) return nullptr;
        // 申请虚拟头节点，需要传出函数。
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;

        // 重载比较方式
        struct cmp {
            bool operator()(ListNode* a, ListNode* b) {
                return a->val > b->val;
            }
        };
		
        // 队列里存放的是链表的头指针，并按照我们自定义的方式排序。
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;

        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i] != nullptr) {   // 需要考虑到空的链表
                pq.push(lists[i]);
            }
        }

        while (!pq.empty()) {
            ListNode* temp = pq.top();
            pq.pop();

            p->next = temp;
            p = p->next;
            
            // 如果当前最小节点的链表后续有节点，加入到队列中排序，这样
            // 就可以得到当前最小的节点
            if (temp->next) {
                pq.push(temp->next);
            }
        }
        return dummy->next;
    }
};

      • 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
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48
      • 49
      • 50
      • 51
      • 52
      • 53
      • 54
      • 55
      • 56

      或者，你可以把所有链表节点值摘下来，放到优先队列里排序（或者你放数组里然后排序都行），然后再重新建立链表

      ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;

        priority_queue<int, vector<int>, greater<int>> pq;
        for (int i = 0; i < lists.size(); ++i) {
            if (lists[i] != nullptr) {
                while (lists[i]) {
                    pq.push(lists[i]->val);
                    lists[i] = lists[i]->next;
                }
            }
        }

        while (!pq.empty()) {
            // 需要重新申请节点，否则无法连接
            p->next = new ListNode(pq.top());
            pq.pop();
            p = p->next;
        }
        return dummy->next;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22

    2.环形链表

    1.判断链表是否有环

    • 解法：这道题，有同学可能采用暴力解法，把链表节点依次放入到数组中，每放入一个就遍历数组查看是否存在该节点，如果存在就有环，否则没有。这样的确可以通过，但是速度会大大折扣，我们这里采用快慢指针的思想。快慢指针，故名思意一个指针走的快，一个走得慢，如果两个指针同时从链表头部开始走，如果有环一定会在某个地方相遇。

      /**
 * 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) {
        ListNode *fast = head;
        ListNode *slow = head;
        // 注意这里，快指针在没有环的情况下，最先到达表尾，且要排除单个节点无环情况
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
};

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24

    2.链表中环的入口结点

    • 解法：在这里插入图片描述

      /*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* slow = pHead, *fast = pHead;
		
        // 大于一个节点才能算环
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }
        
        // 无环情况
        if (fast == nullptr || fast->next == nullptr) return nullptr;

        fast = pHead;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return fast;
    }
};

      • 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
      • 31
      • 32
      • 33
      • 34

      还可以采用哈希来解答，把节点依次加入到哈希中，如果某个元素重复了，那么即为入口。

      #include 
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        unordered_set<ListNode*>set;
        while(pHead){
            if(set.count(pHead)) return pHead; // 也可以使用contains（c++20)
            set.insert(pHead);
            pHead = pHead->next;
        }
        return nullptr;
    }
};

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13

    3.删除链表倒数第N个节点

    • 解法：采用双指针，由于要删除倒数第n个节点，所以我们一定要获取到待删除节点的前一个节点，所以可以让其中一个指针先走n步，然后两个指针同时走，这样当先走的指针走到链表末尾，后走的指针刚刚好走到倒数第n个节点的前一个节点。算法中我们创建一个虚拟节点，这样方便处理删除第一个头节点的情况。
    /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include 
class Solution {
  public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode * dummy =new ListNode(-1);
        dummy->next = head;
        
        ListNode* p1 = dummy, * p2 = dummy;

        if (head == nullptr) return nullptr;
        // 快指针先走n步
        while (n--) {
            p2 = p2->next;
        }
        // 同时走，直到链表结尾
        while (p2->next) {
            p1 = p1->next;
            p2 = p2->next;
        }
        // 删除节点
        p1->next = p1->next->next;
        return dummy->next;
    }
};

    • 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
    • 31

    4.判断两个链表是否相交，相交则返回相交节点

    • 解法： 36
    /*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* L1 = pHead1, *L2 = pHead2;
        while (L1 != L2) {
            L1 = (L1 == nullptr) ? pHead2 : L1->next;
            L2 = (L2 == nullptr) ? pHead1 : L2->next;
        }
        return L1;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    同样也可以用哈希做，但会产生额外空间，同前所述。

    4.删除有序链表中重复的元素

    1.删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次

    • 解法：双指针法，两个指针开始都指向头节点，当后续节点值相同时，快指针向后移动，满指针不动。当节点值不同时，当前慢指针的next指向快指针，然后移动到快指针节点处。

      /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* fast = head, *slow = head;
        while (fast) {
            if (fast->val == slow->val) {
                fast = fast->next;
            } else {
                slow ->next = fast;
                slow = fast;
            }
        }
        slow->next = nullptr;
        return head;
    }
};

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
      • 16
      • 17
      • 18
      • 19
      • 20
      • 21
      • 22
      • 23
      • 24

    2.删除有序链表中重复的元素-II（给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。）

    • 解法：本题是上一道题的进阶版，上一题删除元素让所有元素只出现一次，这道题是，将所有重复的删除。最常规的还是双指针法，一个指针遍历的元素，并设置标志位，标记元素是否重复，一个指针偏移

      /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include 
#include 
class Solution {
  public:

    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(-1);
        if (head == nullptr) return nullptr;
        dummy->next = head;
        bool single = true; // 元素是否是只有一个
        ListNode* p1 = dummy, *p2 = head;
        while(p2->next){
            // 如果p2的当前值和下一个值相同就标记这个元素不是唯一，并移动p2
            if(p2->val == p2->next->val){
                single = false;
                p2=p2->next;
            }
            // 当p2与后面的值不同时，需要判断p2当前指定的值是否是唯一的，
            // 如果不是唯一的，p1的next指向p2的next（注意，此时不移动p1），实现删除重复元素，并重置标记
            // 如果是唯一的，保留元素，那么p1指向p2，并移动到p2，然后p2指向下一个节点。
            else {
                if(!single){
                    p1->next = p2->next;
                    p2 = p2->next;
                    single = true;
                }
                else {
                    p1->next = p2;
                    p1 = p2;
                    p2= p2->next;
                }
            }
        }

        // 出现重复元素后面无其它元素时。
        if(!single){
            p1->next = nullptr;
        }
        return dummy->next;
    }
};

      • 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
      • 31
      • 32
      • 33
      • 34
      • 35
      • 36
      • 37
      • 38
      • 39
      • 40
      • 41
      • 42
      • 43
      • 44
      • 45
      • 46
      • 47
      • 48

    • 解法2：其实这道题还可以使用哈希来做，记录元素出现次数大于1的元素，并删除，重新建立链表

      /**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include 
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == nullptr )return nullptr;
        unordered_map<int,int>map;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;

        ListNode* cur = head;
        // 统计每个元素出现的次数。
        while(cur){
            map[cur->val]++;
            cur = cur->next;
        }

        cur = dummy;
        // 重新建立链表
        while(cur->next){
            if(map[cur->next->val] != 1){
                cur->next = cur->next->next;
            }else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};

      • 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
      • 31
      • 32
      • 33
      • 34
      • 35

    5.判断一个单链表是否为回文结构（正反顺序都一样，例如12321）

    • 解法：前面我们使用了大量的双指针来解题，这个同样可以用双指针来解决，但是由于是单链表，所以我们需要借助数组，来存储元素，然后使用两个指针从数组的两边来对比元素。

      /**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include 
class Solution {
  public:
    bool isPail(ListNode* head) {
        vector<int>vec;
        while (head) {
            vec.push_back(head->val);
            head = head->next;
        }
        int p = vec.size() - 1;
        for (int i = 0;  i < (vec.size() - 1) / 2; ++i) {
            if (vec[i] != vec[p - i]) {
                return false;
            }
        }
        return true;
    }
};

      • 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
  • 相关阅读:
    Nlog详解---非常详细
    Hive篇面试题+详解
    系统学习Python——类（class）代码的编写基础与实例：类可以截获Python运算符
    基于Unity开发的联机解谜游戏的设计与实现
    jmeter实现webservice接口测试
    git命令分之上传项目管理
    Handler的交互场景
    Mac如何安装tensorflow｜from tensorflow.keras.utils import plot_model｜已解决
    iOS重签名-超详细，附排错
    【CFD小工坊】浅水模型的边界条件
  • 原文地址：https://blog.csdn.net/weixin_48617416/article/details/134065330