您现在的位置是:首页 >技术杂谈 >代码随想录算法训练营第四天 | 24.两两交换链表中的节点、19. 删除链表的倒数第 N 个结点、面试题 02.07. 链表相交、142. 环形链表 II网站首页技术杂谈
代码随想录算法训练营第四天 | 24.两两交换链表中的节点、19. 删除链表的倒数第 N 个结点、面试题 02.07. 链表相交、142. 环形链表 II
简介代码随想录算法训练营第四天 | 24.两两交换链表中的节点、19. 删除链表的倒数第 N 个结点、面试题 02.07. 链表相交、142. 环形链表 II
leetcode.24 两两交换链表中的节点
题目描述:给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
分析:挺简单的,只不过要注意空指针问题,因为有点绕很容易就访问到空指针。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* swapPairs(struct ListNode* head){
struct ListNode* dummyHead=(struct ListNode *)malloc(sizeof(struct ListNode));
dummyHead->next=head;
struct ListNode *p=dummyHead;
struct ListNode *pr,*pt;
while(1)
{
if(p->next==NULL)return dummyHead->next;
pr=p->next;
if(pr->next==NULL)return dummyHead->next;
pt=pr->next;
pr->next=pt->next;
pt->next=pr;
p->next=pt;
p=p->next->next;
}
}
leetcode.19. 删除链表的倒数第 N 个结点
题目描述:给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
分析:也挺简单的,一眼有思路。直接先遍历链表求个长度,然后再找倒数第n个元素删除就行。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int getlength(struct ListNode *dummy)
{
int cnt=0;
struct ListNode*p=dummy;
while(p)
{
p=p->next;
cnt++;
}
return cnt;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
struct ListNode* dummy=(struct ListNode*)malloc(sizeof(struct ListNode));
dummy->next=head;
int len=getlength(dummy);
int f=len-n-1;
struct ListNode *p=dummy;
while(f--)
{
p=p->next;
}
p->next=p->next->next;
return dummy->next;
}
leetcode.面试题 02.07. 链表相交
题目描述:给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
。
分析:想了一会都没有思路,看题解写的。就是要将两个链表右对齐,使链表的两个指针处于同一竖直线上,然后一起向下遍历,直到找到结点。还需要注意val相等不等于指针相等。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *pa=headA;
struct ListNode *pb=headB;
int cnta=1,cntb=1;
while(pa!=NULL)
{
pa=pa->next;
cnta++;
}
while(pb!=NULL)
{
pb=pb->next;
cntb++;
}
pa=headA;
pb=headB;
if(cntb>cnta)
{
int tmp=cntb;
cntb=cnta;
cnta=tmp;
struct ListNode *p=pa;
pa=pb;
pb=p;
}
int sub=cnta-cntb;
while(sub--)
{
pa=pa->next;
}
while(pb!=NULL)
{
if(pa==pb)return pa;
pa=pa->next;
pb=pb->next;
}
return NULL;
}
leetcode.142. 环形链表 II
题目描述:给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
分析:还是看的题解做的。第一步:确定有环,解决方法:设置快慢指针,如果有环快指针和慢指针一定会相遇。第二步返回入口节点。推导过程在代码随想录里面有。主要的就是要理解清楚为什么x=z,还有为什么慢指针没走到一圈的时候就被快指针追上了。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode*f=head;
struct ListNode*l=head;
while(f!=NULL&&f->next!=NULL)
{
f=f->next->next;
l=l->next;
if(f==l)
{
struct ListNode *p1=head;
struct ListNode *p2=f;
while(p1!=p2)
{
p1=p1->next;
p2=p2->next;
}
return p1;
}
}
return NULL;
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。