题目练习之链表那些事儿（再续）

class Partition 
{
public:
    ListNode* partition(ListNode* pHead, int x)
    {
        //创建小链表
        ListNode* lessHead, * lessTail;
        //减少代码量，减少判断是否为空操作
        lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));

        //创建大链表
        ListNode* greaterHead, * greaterTail;
        greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));

        //遍历原来的链表
        ListNode* pcur = pHead;
        while (pcur)
        {
            //结点比x小放入小链表(尾插）
            if (pcur -> val < x)
            {
                lessTail->next = pcur;
                lessTail = pcur;
            }
            //结点比x大放入大链表（尾插）
            else
            {
                greaterTail->next = pcur;
                greaterTail = pcur;
            }
            //继续遍历
            pcur = pcur->next;
        }
        //首尾相连
        lessTail->next = greaterHead->next;
        //大链表尾结点下一个结点置为空，避免死循环
        greaterTail->next = NULL;
        //保存返回的结点
        ListNode* reNode = lessHead->next;
        //释放动态申请的空间（一块空间释放一次就可以了）
        free(lessHead);
        lessHead = NULL;
        free(greaterHead);
        greaterHead = NULL;

        //返回结点
        return reNode;
    }
}

typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
	//特殊处理，如果有一个为空直接返回NULL
	//分开处理
	if (headA == NULL)
	{
		return NULL;
	}
	if (headB == NULL)
	{
		return NULL;
	}
  //遍历两个链表统计结点个数
	ListNode* pcurA = headA;
	ListNode* pcurB = headB;

	int sizeA = 0;
	int sizeB = 0;
	while (pcurA)
	{
		sizeA++;
		pcurA = pcurA->next;
	}
	while (pcurB)
	{
		sizeB++;
		pcurB = pcurB->next;
	}

	//求结点差gap
	int gap = abs(sizeA - sizeB);
	//abs求绝对值，头文件math.h
	
	//假设长链表和短链表
	ListNode* LongList = headA;
	ListNode* ShortList = headB;
	//另外一种情况
	if (sizeA < sizeB)
	{
		LongList = headB;
		ShortList = headA;
	}
	//长链表先走gap步
	while (gap--)
	{
		LongList = LongList->next;
	}
	//长链表和短链表在同一起跑线，剩下的结点个数相同
	//遍历两个链表比较
	while (LongList)//或者while (ShortList)  //剩下的结点数相同都可以
	{
		if (LongList == ShortList)
		{
			return LongList;
			//或者return ShortList
		}
		LongList = LongList->next; 
		ShortList = ShortList->next;
	}
	//结束也没有相同结点，返回NULL
	return NULL;
}

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode* head) {

    //使用快慢指针
    ListNode* slow = head;
    ListNode* fast = head;
    //快指针每次走两步
    //慢指针每次走一步
    while (fast && fast->next)
    {
        //先往后面走再比较，因为最开始slow和fast都是指向head
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            //快慢指针相遇会带环
            return true;
        }
       
    }
    //走到NULL，不带环
    return false;
}

typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
   //快慢指针到相遇点
	ListNode* slow = head;
	ListNode* fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast)//带环，到达相遇点
		{
			ListNode* pcur = head;
			//一个指针从头结点开始走
			//一个指针从相遇点开始走
			//两个指针一定会相遇
			while (pcur != slow)
			{
				pcur = pcur->next;
				slow = slow->next;
			}
			//相遇点就是入口点
			return pcur;
            //或者return slow;
		}
	}
	//不带环返回NULL
	return NULL;
}

typedef struct Node Node;
Node* buyNode(int x)
{
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL)
    {
        perror("malloc fail\n");
    }
    else
    {
        newNode->val = x;
        newNode->next = newNode->random = NULL;
    }
    return newNode;
}
void addNode(Node* head)
{
    //head不会为空
    Node* pcur = head;
    //遍历接结点
    while (pcur)
    {
        //保存原来链表当前结点的下一个结点
        Node* Next = pcur->next;
        //拷贝结点
        Node* addnode = buyNode(pcur->val);
        pcur->next = addnode;
        addnode->next = Next;
        pcur = Next;
    }
}
struct Node* copyRandomList(struct Node* head)
{
    //特殊处理链表为空
    if (head == NULL)
    {
        return NULL;
    }
    //拷贝每一个结点到当前结点后面
    addNode(head);
    //处理random指针
    Node* pcur = head;
    while (pcur)
    {
        //找到拷贝的结点
        Node* copy = pcur->next;
        if (pcur -> random != NULL)
        {
            //random为原来链表random的下一个指向
            copy->random = pcur->random->next;
        }
        //往后面遍历处理
        pcur = copy->next;
    }
    //断开新旧链表
    pcur = head;
    //pcur重新指向头结点
    Node* newTail, * newHead;
    //从拷贝的第一个结点开始
    newTail = newHead = pcur->next;
    while (newTail->next)
    {
        pcur = newTail->next;
        newTail->next = pcur->next;
        newTail = newTail->next;
    }
    return newHead;
}