数据结构：链表分割、相交与环检测算法

一、链表分割

题目链接：NowCoder

题目要求将链表分割，值小于 x 的节点放在左边，大于等于 x 的节点放在右边。

解题思路： 创建两个新链表（小链表和大链表），使用哨兵位节点占位以避免空链表判断。遍历原链表，将节点分别接入对应链表，最后连接小链表尾与大链表头，并释放哨兵节点。

ListNode* partition(ListNode* pHead, int x) {
    ListNode* lesshead = NULL, *lesstail = NULL;
    ListNode* greaterhead = NULL, *greatertail = NULL;
    
    // 初始化哨兵节点
    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);
    return ret;
}

二、相交链表

题目链接：LeetCode

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

解题思路： 由于两链表长度可能不同，直接遍历无法保证同时到达相交点。先计算两链表长度，让长链表先走长度差步数，使两指针处于同一起跑线，然后同步遍历。若相遇则返回该节点，否则返回 NULL。

struct ListNode* getIntersectionNode( ListNode* headA,  ListNode* headB) {
     * pcurA = headA;
     * pcurB = headB;
     countA = , countB = ;
    
    
    (pcurA) { countA++; pcurA = pcurA->next; }
    (pcurB) { countB++; pcurB = pcurB->next; }
    
    
     * lesslist = headA;
     * greaterlist = headB;
    (countA > countB) {
        lesslist = headB;
        greaterlist = headA;
    }
    
    
     size = (countA - countB);
    (size--) {
        greaterlist = greaterlist->next;
    }
    
    
    (lesslist) {
        (lesslist == greaterlist)  lesslist;
        lesslist = lesslist->next;
        greaterlist = greaterlist->next;
    }
     ;
}