链表分割|链表的回文结构|相交链表|环形链表|随机链表的复制(C)

链表分割_牛客题霸_牛客网

x=3
小于3的尾插到第一条链表，大于等于3的尾插到第二条链表，最后把两个链表连接起来
带哨兵位头节点会更简单，不用考虑哪个链表为空的情况

直接让ltail的next指向ghead的next

• 若第一个链表为NULL
  

也是ltail的next指向ghead的next

• 有可能出现带环链表
  

所以还需要将gtail的next置空

ListNode* partition(ListNode* pHead, int x) {
    struct ListNode* ghead, *gtail, *lhead, *ltail;
    ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
    lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
  
    struct ListNode* cur = pHead;
    while (cur)
    {
        if (cur->val < x)
        {
            ltail->next = cur;
            ltail = ltail->next;
        }
        else
        {
            gtail->next = cur;
            gtail = gtail->next;
        }
  
        cur = cur->next;
    }
  
    ltail->next = ghead->next;
    
    gtail->next = NULL;
    
    struct ListNode* head = lhead->next;
    free(lhead);
    free(ghead);
  
    return head;
    }

free哨兵位之前需要将头节点保存下来

链表的回文结构_牛客题霸_牛客网

通过快慢指针，找到链表的中间位置，将链表的后半部分逆置，然后两个指针一个从头，另一个从中间开始，挨个比较

• 有奇数个数据
  

虽然后半部分逆置了，但是2的next还是存的3的地址
2可以不置空

• 偶数个数据
  

//找到中间节点
struct ListNode* middleNode(struct ListNode* head)
{
	struct ListNode* slow = head, *fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	return slow;
}

//逆置
struct ListNode* reverseList(struct ListNode* head)
{
	struct ListNode* cur = head;
	struct ListNode* newhead = NULL;

	while (cur)
	{
		struct ListNode* next = cur->next;

		cur->next = newhead;
		newhead = cur;

		cur = next;
	}

	return newhead;
}

//判断回文
bool chkPalindrome(ListNode* A) {
	struct ListNode* mid = middleNode(A);
	struct ListNode* rmid = reverseList(mid);
	while (rmid && A)
	{
		if (rmid->val != A->val)
		{
			return false;
		}
		rmid = rmid->next;
		A = A->next;
	}

	return true;
}

160. 相交链表

判断尾节点的地址是否相同，来判断是否相交
尾节点相等就相交，不相等就不相交

找交点，用一个链表的值，去另外一个链表找一遍，比的是地址
第一个相等的就是交点

时间复杂度是$O(n^2)$

1. 计算出两个A，B的长度，记为lenA，lenB
2. 长的链表先走差距步abs(lenA-lenB)
3. 不一样长的是前半段，走完差距步后，可以认为后半段是一样长的
   一样长的话，之后依次比对就可以了，不需要逐个比对
   如果不相等往后走，第一个相等的就是交点
   

时间复杂度是$O(N)$

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA, *curB = headB;
    int lenA = 1, lenB = 1;
    while (curA->next)
    {
        curA = curA->next;
        ++lenA;
    }
    while (curB->next)
    {
        curB = curB->next;
        ++lenB;
    }
  
    //尾节点不相等，不相交
    if (curA != curB)
    {
        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 (longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
  
    return longList;
}

141. 环形链表

入环节点可以是任意一个节点，可以是头节点，中间节点或尾节点

如何判断是否链表带环

用两个指针，

slow一次走一步，fast一次走两步

slow到中间位置，fast刚好进环

slow刚进环，此时两个指针都进环了
两个指针一个快，一个慢，开始追击

当两个指针相遇，就代表有环

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

一定可以追上

slow刚到交点时，slow和fast的距离是N

追击一次以后，之间的距离-1
当slow进环以后，fast开始追击slow，假设slow入环时，之间的距离是N
每追击一次，他们之间的距离缩小1
距离的变化：
N，N-1，N-2，…，2，1，0
当距离为0时，代表相遇

142. 环形链表 II

求环的入口点

思路1

假设起点到入口点长度是L
假设环的周长是C
假设从入口点到相遇点的距离是x
fast走的路程是slow的距离的二倍

slow走的距离：L+x
x的距离一定小于C，因为如果x大于C，fast走的距离一定大于2C，早就追上了

slow进环后一圈内，fast一定追上slow
slow进环时，假设fast在环里走了n圈
如果不足n圈，追的时候会补足n圈然后加上x
fast走的距离：L+n*C+x
$2(L+x)=L+n\cdot C+x$
$L=n\cdot C-x$

一个指针从起点开始走，一个指针从相遇点走，会在入口点相遇

一个指针从相遇点走，走了(N-1)圈，之后走了(C-x)

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

思路2

找到相遇点之后
将环从相遇点断开

将newhead指针指向相遇点的下一个节点，然后断开newhead和meet指针指向的节点

newhead = meet->next;
meet->next = NULL;

这个时候求入口点就相当于求相交链表的交点

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA, *curB = headB;
    int lenA = 1, lenB = 1;
    while (curA->next)
    {
        curA = curA->next;
        ++lenA;
    }
    while (curB->next)
    {
        curB = curB->next;
        ++lenB;
    }
  
    //尾节点不相等，不相交
    if (curA != curB)
    {
        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 (longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
  
    return longList;
}
  
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow, *fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
  
        if (slow == fast)
        {
            struct ListNode* meet = slow;
            struct ListNode* newhead = meet->next;
            meet->next = NULL;
  
            return getIntersectionNode(newhead, head);
        }
    }
  
    return NULL;
}

138. 随机链表的复制

单链表+随机指针
不可以拿值来比对，链表中可以有相同的值
![[Pasted image 20241029100306.png]]
找对应的random一定要找相对位置

思路1

暴力求解的时间复杂度$O(N^2)$

1. 复制链表
2. 算random在原链表的相对位置，控制复制链表

思路2

1. 将拷贝节点插入到原节点的后面
   

每个拷贝节点都在原节点的后面
2. 置每个拷贝节点的random指针
7的random指向NULL
7的next的节点也指向空
13的random指向7
13的next的节点指向7的next的节点
…

copy->random = cur->random->next

3. 拷贝节点解下来，尾插到一起，回复原链表

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur = head;
    while (cur)
    {
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
  
        // 插入
        cur->next = copy;
        copy->next = next;
  
        // 往后走
        cur = next;
    }
  
    cur = head;
    while (cur)
    {
        struct Node* copy = cur->next;
  
        // 置copy的random
        if (cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;
        
        cur = copy->next;
    }
  
    cur = head;
    struct Node* copyhead = NULL, *copytail = NULL;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
  
        // copy节点尾插到新链表
        if (copytail == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }
  
        // 恢复原链表
        cur->next = next;
  
        cur = next;
    }
  
    return copyhead;
}