LeetCode 链表专题：分割、相交及环形链表 C++ 解法

一、链表分割

题目链接：链表分割

题目描述如下：

本题基于 C++ 类实现，代码编写位置遵循题目提示。

题目要求将链表分割，值小于 x 的节点放在左边，大于等于 x 的节点放在右边。方法类似双指针算法。我们可以创建两个新链表，分别存放比 x 小的节点和比 x 大或相等的节点，最后连接。

为避免空链表判断繁琐，使用哨兵节点占位，无需判断链表是否为空。

解题思路：创建大小链表及哨兵位，遍历原链表分配节点，连接首尾。

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* lesshead, *lesstail;
        ListNode* greaterhead, *greatertail;
        lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
        greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* pcur = pHead;
        while(pcur) {
            if(pcur->val < x) {
                lesstail->next = pcur;
                lesstail = pcur;
            } else {
                greatertail->next = pcur;
                greatertail = pcur;
            }
            pcur = pcur->next;
        }
        lesstail->next = greaterhead->next;
        greatertail->next = NULL;
        ListNode* ret = lesshead->next;
        free(lesshead);
        free(greaterhead);
        lesshead = NULL;
        greaterhead = NULL;
        return ret;
    }
};

二、相交链表

题目链接：相交链表

题目要求判断两链表是否相交，若相交返回相交节点，否则返回空。

链表相交后只有一个方向。若同时开始遍历，因长度不同可能无法相遇。需计算长度差，让长链表先走差距步，再同步遍历。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1, lenB = 1;
    while(tailA->next) { tailA = tailA->next; ++lenA; }
    while(tailB->next) { tailB = tailB->next; ++lenB; }
    if(tailA != tailB) return NULL;
    int gap = abs(lenA - lenB);
    struct ListNode* longlist = headA, *shortlist = headB;
    if(lenA < lenB) { longlist = headB; shortlist = headA; }
    while(gap--) { longlist = longlist->next; }
    while(shortlist) {
        if(longlist == shortlist) return longlist;
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return NULL;
}

三、环形链表 I

题目链接：环形链表 |

带环指尾结点的 next 指针指向链表中某个节点。

本题只需判断是否有环。基于快慢指针结论：若带环，快指针（一次两步）和慢指针（一次一步）必在环内相遇。

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

四、环形链表 II

题目链接：环形链表 ||

本题还需找出入环的第一个节点。

结论：相遇节点到入环节点的距离，等于头结点到入环节点的距离。即头结点与慢指针同时同速前进，相遇处即为入环点。

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