【每日刷题】Day23
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 138. 随机链表的复制 - 力扣（LeetCode）
2. 链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
3. 237. 删除链表中的节点 - 力扣（LeetCode）
1. 138. 随机链表的复制 - 力扣（LeetCode）
//这题对深拷贝不了解的需要先去了解一下，不然很难写这道题。
//思路：首先创建一个标准新链表，先不管random指针，就将原链表的val存入新链表。然后使用一个数组存储原链表每个节点的地址。随后处理random，遍历原链表的random，去数组中寻找，没找到就让新链表向后遍历一位，当找到时，新链表的指针也指向了random指向的地址。
typedef struct Node SN;
struct Node* copyRandomList(struct Node* head)
{
if(!head)
{
return NULL;
}
SN* pmove = head;
SN* pmove1 = head;
SN* pnewhead = (SN*)malloc(sizeof(SN));
SN* newmove = pnewhead;
while(pmove)
{
SN* newnode = (SN*)malloc(sizeof(SN));
newnode->next = NULL;
newnode->val = pmove->val;
newmove->next = newnode;
pmove = pmove->next;
newmove = newmove->next;
}
SN* newmove1 = pnewhead->next;
SN* arr[2000];
int i = 0;
while(head)
{
arr[i++] = head;
head = head->next;
}
SN* phead = newmove1;
while(pmove1)
{
SN* pmove2 = phead;
int j = 0;
while(pmove1->random!=arr[j]&&pmove2)
{
pmove2 = pmove2->next;
j++;
}
newmove1->random = pmove2;
pmove1 = pmove1->next;
newmove1 = newmove1->next;
}
return pnewhead->next;
}
2. 链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
//思路：得到链表的中间节点，将链表的后半段反转，再创建一个指向链表头节点的指针。指向链表中间节点的指针，两个指针同时走，比较val，val不相等直接返回false，都相等就返回true，只要有一个指针为NULL就停止循环。
class PalindromeList
{
public:
struct ListNode* FindMid(struct ListNode* A)//得到指向链表中间节点的指针
{
struct ListNode* fast = A;
struct ListNode* slow = A;
while(fast&&fast->next)
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)//将链表后半段反转
{
if(head==NULL||head->next==NULL)
{
return head;
}
struct ListNode* pf1 = NULL;
struct ListNode* pf2 = head;
struct ListNode* pf3 = pf2->next;
while(pf2->next)
{
pf2->next = pf1;
pf1 = pf2;
pf2 = pf3;
pf3 = pf3->next;
}
pf2->next = pf1;
pf1 = pf2;
return pf1;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode* mid = FindMid(A);//mid为指向链表中间节点的指针
struct ListNode* cur = reverseList(mid);//传mid以反转后半段
while(A&&cur)//循环逐个比较val
{
if(A->val!=cur->val)
{
return false;
}
A = A->next;
cur = cur->next;
}
return true;
}
};
3. 237. 删除链表中的节点 - 力扣（LeetCode）
//思路：创建新链表。这道题的难点在于无法使用头节点对链表进行访问，因此我们可以想到通过改变需要删除节点来达到删除的目的。这里我们创建一个新的链表，新的链表存储的是要删除节点后的数据，然后将要删除节点中的值改为新链表头节点的值，要删除节点的next指针的指向改为新链表的第二个节点。
typedef struct ListNode LN;
void deleteNode(struct ListNode* node)
{
LN* pmove = node->next;//指向要删除节点的下一个节点
LN* pnewhead = (LN*)malloc(sizeof(LN));//新链表的哨兵位
LN* phead = pnewhead;
while(pmove)//将要删除节点后面的节点中的值存入新链表
{
phead->next = pmove;
pmove = pmove->next;
phead = phead->next;
}
node->val = pnewhead->next->val;//将要删除节点的val改为新链表头节点的val
node->next = pnewhead->next->next;next指针指向新链表的第二个节点
}
