【每日刷题】Day16
【每日刷题】Day16
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 24. 两两交换链表中的节点 - 力扣（LeetCode）
2. 160. 相交链表 - 力扣（LeetCode）
3. 136. 只出现一次的数字 - 力扣（LeetCode）
1. 24. 两两交换链表中的节点 - 力扣（LeetCode）
//0ms 100％思路：创建新链表，malloc新节点按照题目所给顺序存储原链表节点，新链表逐个连接新节点
typedef struct ListNode LN;
int ListNodeQua(LN* phead)//计算原链表节点数
{
LN* pmove = phead;
int count = 0;
while(pmove)
{
count++;
pmove = pmove->next;
}
return count;
}
struct ListNode* swapPairs(struct ListNode* head)
{
if(head==NULL)
{
return NULL;
}
if(head->next==NULL)
{
return head;
}
int n = ListNodeQua(head);
LN* sentry = (LN*)malloc(sizeof(LN));//新链表哨兵位
LN* pmove = head;//原链表奇数位节点
LN* pmove1 = sentry;//用于遍历新链表连接新节点
int i = 0;
while(i<n/2)//交换次数即为循环次数
{
LN* pmove2 = pmove->next;//原链表偶数位节点
LN* pget1 = (LN*)malloc(sizeof(LN));//新节点1
pget1 = pmove2;//存储原链表偶数位节点
pmove1->next = pget1;//连接新节点
pmove1 = pmove1->next;//往后遍历以连接下一个节点
LN* pget2 = (LN*)malloc(sizeof(LN));//新节点2
pget2 = pmove;//存储原链表奇数位节点
pmove->next = pmove2->next;//这里需要注意，由于原链表奇数位节点的next指向后一个偶数位节点，而下面我们在让新链表连接新节点时，会导致相邻两个节点成环，因此这里需要在新链表连接新节点前让奇数位节点的next指向下一个奇数位节点
pmove1->next = pget2;//连接新节点
pmove1 = pmove1->next;//往后遍历以连接下一个节点
pmove = pmove->next;//由于上面我们奇数位节点next指向了下一个奇数位节点，因此这里直接走向next即可进行下一个交换
i++;
}
LN* phead = head;
if(n%2==1)//如果链表个数为奇数个，则在最后一次交换后会遗漏下最后一个节点，这里只需要直接将最后一个节点连接上即可
{
while(phead->next)
{
phead = phead->next;
}
pmove1->next = phead;
}
return sentry->next;
}
2. 160. 相交链表 - 力扣（LeetCode）
//思路：根据题目要求我们容易想到用两个指针遍历两个链表，当指针相等时就是相交的起始节点，直接返回。但是也容易发现一个问题，链表的长度不是严格相等的，因此，若是两个指针都在第一个节点同时遍历则可能会错过。那么我们这里的思路就是如何让两个指针刚好相遇——让较长的链表的指针先走过两链表长度差值的节点数。
typedef struct ListNode LN;
int ListNodeQua(LN* phead)//计算链表节点数
{
LN* pmove = phead;
int count = 0;
while(pmove)
{
count++;
pmove = pmove->next;
}
return count;
}
int my_abs(int x,int y)//返回两链表节点数差值（正数）
{
return x>y?x-y:y-x;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
if(headA==NULL||headB==NULL)
{
return NULL;
}
LN* pf1 = headA;
LN* pf2 = headB;
int a = ListNodeQua(headA);//链表A的节点数
int b = ListNodeQua(headB);//链表B的节点数
int x = my_abs(a,b);//两链表节点数差值的绝对值
int flag = a>b?1:0;//用于判断需要哪个链表的指针走
while(x)
{
if(flag)//如果flag为1，则说明链表A较长，则让pf1的指针走过x个节点
{
pf1 = pf1->next;
}
else//否则则是链表B较长，让pf2走过x个节点
{
pf2 = pf2->next;
}
x--;
}
while(pf1&&pf2)//这时再让pf1、pf2同时走，相遇时直接返回
{
if(pf1==pf2)
{
return pf1;
}
pf1 = pf1->next;
pf2 = pf2->next;
}
return NULL;
}
3. 136. 只出现一次的数字 - 力扣（LeetCode）
//思路：这里需要知道的知识——
1、0^上任何数都等于任何数本身
2、两个相同的数^起来等于0
知道了这两个知识后，这道题就变得非常简单，因为数组中只有一个数字出现一次，其余的数字均出现了两次，那么我们用一个数（初始为0）^上这个数组中的每一个数，相同的数^在一起变为0，则^到最后就会变成0^上那个只出现了一次的数，而0^上任何数等于任何数，则直接返回最终^的结果即可
int singleNumber(int* nums, int numsSize)
{
int num = 0;
for(int i = 0;i<numsSize;i++)
{
num^=nums[i];
}
return num;
}