C++ 链表题型

ゝ一世哀愁。 2023-06-06 08:27 15阅读 0赞

**目录**

链表题目：

1.从尾到头打印链表

2.链表的倒数第k个结点

3. 翻转链表

4.合并2 个有序的链表

5. 两个链表的第一个公共结点

6. 链表中环的入口

7. 删除链表中重复的节点

--------------------

## 链表题目： ##

### 1.从尾到头打印链表 ###

/**
    *  struct ListNode {
    *        int val;
    *        struct ListNode *next;
    *        ListNode(int x) :
    *              val(x), next(NULL) {
    *        }
    *  };
    */
    class Solution {
    public:
        vector<int> printListFromTailToHead(ListNode* head) {
            // 使用栈来保存
            if (head == nullptr) return vector<int>();
            stack<int> mystack;
            vector<int> res;
            ListNode* p = head;
            while (p != nullptr){
                mystack.push(p->val);
                p = p->next;
            }
            while (!mystack.empty()){
                res.push_back(mystack.top());
                mystack.pop();
            }
            return res;
            
        }
    };

### 2.链表的倒数第k个结点 ###

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            // 设置一个结点先走k步，然后一起走
            if (pListHead == nullptr) return NULL;
            if (k < 0) return NULL;
            ListNode* p = pListHead;
            for (int i = 0; i< k-1; i++){
                p = p->next;
                if (p == nullptr) return NULL;
            }
            while (p->next != nullptr){
                p = p->next;
                pListHead = pListHead->next;
            }
            return pListHead;
        
        }
    };

### 3. 翻转链表 ###

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* ReverseList(ListNode* pHead) {
            if (pHead == nullptr || pHead-> next == nullptr) return pHead;
            ListNode* p = pHead;
            ListNode* newP = NULL;
            ListNode* temp = NULL;
            while (p){
                temp = p->next;
                p->next = newP;
                newP = p;
                p = temp;
            }
            return newP;
        
        }
    };

递归的形式翻转链表：

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* ReverseList(ListNode* pHead) {
            // 使用递归的方法来翻转一个链表
            if (pHead == nullptr || pHead->next == nullptr){
                return pHead;
            }
            ListNode* reversedP;
            reversedP = ReverseList(pHead->next);
            pHead->next->next = pHead;
            pHead->next = NULL;
            
            return reversedP;
    
        }
    };

### 4.合并2 个有序的链表 ###

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
        {
            // 使用递归的方法合并连个有序的链表
            if (pHead1 == nullptr && pHead2 != nullptr){
                return pHead2;
            }
            if (pHead2 == nullptr && pHead1 != nullptr){
                return pHead1;
            }
            
            if (pHead1 == nullptr && pHead2 == nullptr){
                return NULL;
            }
            ListNode* ret = NULL; // 先在外部进行声明
            
            if (pHead1->val >= pHead2-> val){
                ret = pHead2;
                ret->next = Merge(pHead1, pHead2->next);
            }else{
                ret = pHead1;
                ret->next = Merge(pHead1->next, pHead2);
            }
            return ret;
            
            
            
        }
    };

### 5. 两个链表的第一个公共结点 ###

/*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
            // 先计算2 个链表的长度，然后计算差值k，短的先走k步，然后一起走，知道有相同的结点
            if (pHead1 == nullptr || pHead2 == nullptr){
                return NULL;
            }
            int len1= 0;
            int len2 = 0;
            ListNode* move1 = pHead1;
            ListNode* move2 = pHead2;
       
            while (move1 != nullptr){
                len1 ++;
                move1 = move1->next;
            }
            
            while (move2 != nullptr){
                len2++;
                move2 = move2->next;
            }
            
            while (len1 > len2){
                len1 --;
                pHead1 = pHead1->next;
            }
            
            while (len1 < len2){
                len2 --;
                pHead2 = pHead2->next;
            }
            // 一起往前走
            while (pHead1 != nullptr){
                if (pHead1 == pHead2){
                    return pHead1;
                }else{
                    pHead1 = pHead1->next;
                    pHead2 = pHead2->next;
                }
            }
            
        }
    };

### 6. 链表中环的入口 ###

设置快慢结点，找到相遇的结点；然后首结点和相遇的节点一起往前走，直到找到相交的结点。

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
    public:
        ListNode* EntryNodeOfLoop(ListNode* pHead)
        {
            // 设置快慢结点，走1 步和走2步，找到相遇的结点q； 然后q 和头部结点一起往前走，直到找到相遇的结点；
            if (!pHead || !pHead->next || !pHead->next->next) return NULL;
            ListNode* low = pHead->next;
            ListNode* fast = pHead->next->next;
            while (low != fast){
                if (!low->next || !fast->next->next) return NULL;
                low = low->next;
                fast = fast->next->next;
            }
            
            while (fast != pHead){
                pHead = pHead->next;
                fast = fast->next;
            }
            return pHead;
    
        }
    };

### 7. 删除链表中重复的节点 ###

重复的结点全部删除

1. 设置dummy 结点； 2. 设置一个 前置结点last 和当前结点 pHead， 使用last -> next 指向pHead ,即删除结点

3. 设置初始的判断条件是 while (pHead && pHead -> next)

> 创建一个结点： ListNode\* node = new ListNode(-1);

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) :
            val(x), next(NULL) {
        }
    };
    */
    class Solution {
    public:
        ListNode* deleteDuplication(ListNode* pHead)
        {
            if (!pHead || !pHead->next) return pHead;
            // 创建一个dummy 结点
            ListNode* first = new ListNode(-1);
            first->next = pHead;
            ListNode* last = first;
            
            while(pHead && pHead->next){
                if (pHead->val == pHead->next->val){
                    int values = pHead->val;
                    while (pHead && pHead->val == values){
                        pHead = pHead->next;
                    }
                    last->next = pHead;
                }else{
                    last = last->next;
                    pHead = pHead->next;
                }
            }
            return first->next;
    
        }
    };

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20230601/c9f069766f3a4dccaa7dfc03dd4812a8.png