单链表常见算法题解析：反转、合并与环检测

单链表常见算法题涉及反转、中间节点查找、合并有序链表、回文结构判断、相交节点检测及环形链表判定。主要采用快慢指针、头插法、尾插法及数组辅助等策略解决。重点讲解双指针在遍历和环检测中的应用逻辑，以及处理空指针边界条件的注意事项，提供 C++ 代码实现参考。

二进制发布于 2026/3/15更新于 2026/4/184 浏览

1. 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/

题目：

文章配图

看到这个题目的时候我们怎么去想呢？如果我们反应快的话，应该可以想到我们可以从 1 遍历到 5 然后依次头插，但是其实我们还有更好的办法，就是利用三个指针，如何使用呢？

文章配图

// 反转链表 OJ 假如结构体已经给出
typedef struct ListNode SL;
SL* reverseList(SL* head) {
    // 处理空链表
    if (head == NULL) {
        return head;
    } else {
        // 创建三个指针
        SL* n1, n2, n3;
        n1 = NULL, n2 = head, n3 = n2->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3) {
                n3 = n3->next;
            }
        }
        return n1;
    }
}

文章配图

2. 链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

题目：这个题目就是在一个链表中我们要返回中间结点，如果中间结点有两个的话就返回第二个结点。

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

// 找链表的中间结点
// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};
typedef struct ListNode SL;
struct ListNode* middleNode(struct ListNode* head) {
    SL* slow = head;
    SL* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode SL;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 创建新的链表
    SL* newhead=NULL;
    SL* newtail=NULL;
    // 创建两个指针分别指向两个链表
    SL* l1=list1;
    SL* l2=list2;
    // 判断两个链表是否为空
    if(list1==NULL) {
        return l2;
    }
    if(list2==NULL) {
        return l1;
    }
    while(l1&&l2) {
        if(l1->val<=l2->val) {
            // l1 尾插到新链表中
            if(newhead==NULL) {
                newhead=newtail=l1;
            } else {
                newtail->next=l1;
                newtail=newtail->next;
            }
            l1=l1->next;
        } else {
            // l2 尾插到新链表中
            if(newhead==NULL) {
                newhead=newtail=l2;
            } else {
                newtail->next=l2;
                newtail=newtail->next;
            }
            l2=l2->next;
        }
    }
    // 跳出循环有两种情况，要么 l1 为空，要么 l2 为空
    if(l1) {
        newtail->next=l1;
    }
    if(l2) {
        newtail->next=l2;
    }
    return newhead;
}

/* struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {} 
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        // 创建一个数组
        int arr[900] = {0};
        ListNode* pcur = A;
        int i = 0;
        // 遍历链表，将链表中的每个结点的数值放入数组中
        while(pcur) {
            arr[i++] = pcur->val;
            pcur=pcur->next;
        }
        // 找中间结点，判断是否是回文数字
        int left=0;
        int right=i-1;
        while(left<right) {
            if(arr[left]!=arr[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    // 创建两个指针遍历链表
    ListNode* l1=headA;
    ListNode* l2=headB;
    // 先计算两个链表的长度
    int sizeA=0;
    int sizeB=0;
    while(l1) {
        sizeA++;
        l1=l1->next;
    }
    while(l2) {
        sizeB++;
        l2=l2->next;
    }
    // 得出了两个链表的长度
    // 计算两数之差
    int gap=abs(sizeA-sizeB);
    // 让长链表先走 gap 步
    ListNode* longlist=headA;
    ListNode* shortlist=headB;
    if(sizeA<sizeB) {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--) {
        longlist=longlist->next;
    }
    // 此时在同一个起点处，进行两个链表结点的比较
    while(longlist&&shortlist) {
        if(longlist==shortlist) {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    // 链表不相等
    return NULL;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode SL;
bool hasCycle(struct ListNode *head) {
    SL* slow=head;
    SL* fast=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. 环形链表

单链表常见算法题解析：反转、合并与环检测

1. 反转链表

2. 链表的中间结点

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

3. 合并两个有序链表

4. 链表的回文结构

5. 相交链表

6. 环形链表