【算法】链表算法题子集：链表翻转、K个一组翻转、有无环、环形入口节点

CS_Zero

已于 2024-07-19 16:11:44 修改

阅读量677

点赞数 17

分类专栏： Programming LeetCode 文章标签：链表数据结构

于 2024-03-13 19:26:46 首次发布

本文链接：https://blog.csdn.net/CSUzhangpeike/article/details/136689021

版权

本文汇总了关于链表的三类算法问题：1. 翻转链表，介绍了启发式和递归两种解法；2. K 个一组翻转链表，通过计数和栈完成分段翻转；3. 环形链表问题，包括判断环的存在及寻找环的入口节点，利用快慢指针进行高效解决。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1. 翻转链表

题目链接
常用两种思路，第一种是启发式，
测试用例

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

第2种方法是递归，

ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* ans = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
 }

2. K 个一组翻转链表

K 个一组翻转链表题目链接
基本思路：用计数+栈实现分段，K个一组地翻转链表。

#include <bits/stdc++.h>
#include <stack>
using namespace std;

struct list_node {
   
  int val;
  struct list_node *next;
};

list_node *input_list() {
   
  int val, n;
  scanf("%d", &n);
  list_node *phead = new list_node();
  list_node *cur_pnode = phe

最低0.47元/天解锁文章