数据结构与算法中链表相交及环形链表相关探索

数据结构与算法中链表相交及环形链表的相关探究

1.相交链表

题目

给定两个单链表的头节点 headA 和 headB，请找出并返回两个单链表相交的起始节点。若两个链表不存在相交节点，返回 null。

示例

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at ‘8’
解释：相交节点的值为 8。链表 A 从表头开始前 2 个节点后进入相交部分，链表 B 从表头开始前 3 个节点后进入相交部分。需注意值为 1 的节点在两链表中内存位置不同，而值为 8 的节点内存位置相同。

分析

可采用双指针思路解决。首先计算两链表长度，让较长链表先走完多余节点数，之后两链表同步遍历，当节点相同时即为相交节点。具体步骤：
1. 计算两链表长度，判断哪个更长。
2. 较长链表先移动多余的节点数。
3. 两链表同步移动，直到找到相同节点或遍历完。

代码实现

//先求两个链表的长度，判断谁长谁短，长的长多少
Node* curA = headA;
Node* curB = headB;
int sizeA = 1;
int sizeB = 1;
while(curA)
{
    sizeA++;
    curA = curA->next;
}
while(curB)
{
    sizeB++;
    curB = curB->next;
}

//判断谁长，长的先走完长的步数
if(sizeA > sizeB)
{
    int lenth_sub = sizeA - sizeB;
    while(lenth_sub--)
    {
        headA = headA->next;
    }
    //之后同时走
    while(headA != headB)
    {
        if(headA == NULL)
            return NULL;
        headA = headA->next;
        headB = headB->next;
    }
    return headA;
}
else
{
    int lenth_sub = sizeB - sizeA;
    while(lenth_sub--)
    {
        headB = headB->next;
    }
    while(headA != headB)
    {
        if(headA == NULL)
            return NULL;
        headA = headA->next;
        headB = headB->next;
    }
    return headA;
}

2.环形链表（判断是否有环）

题目

给定一个链表的头节点 head，判断链表中是否有环。若链表中存在环，返回 true；否则，返回 false。

示例

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

分析

采用快慢指针方法。快指针每次走两步，慢指针每次走一步。若链表存在环，快指针最终会追上慢指针；若快指针遍历完链表仍未追上慢指针，则链表无环。

代码实现

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast = head , *slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
            return true;
    }
    return false;
}

3.环形链表（返回入环节点）

题目

给定一个链表的头节点 head，返回链表开始入环的第一个节点。若链表无环，则返回 null。且不允许修改链表。

示例

示例1：输入：head = [3,2,0,-4], pos = 1，输出：返回索引为 1 的链表节点
解释：链表存在环，尾部连接到第二个节点。
示例2：输入：head = [1], pos = -1，输出：返回 null
解释：链表中没有环。

分析

在判断链表有环的基础上，利用快慢指针相遇后，让一个指针从头节点出发，另一个指针从相遇点出发，两者同步移动，再次相遇时的节点即为环的入口节点。原理是头节点到环入口的距离等于相遇点到环入口的距离加上整数倍的环长。

代码实现

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast = head , *slow = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(slow == fast)
        {
            while(head != fast)
            {
                head = head->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}

总结

本文介绍了三道链表相关题目，包括相交链表的查找、环形链表是否存在的判断以及环形链表入口节点的查找。这些题目通过双指针等方法解决，拓展了数据结构与算法的知识，希望读者能从中有所收获。