个人主页 : zxctsclrjjjcph
文章封面来自:艺术家–贤海林
如有转载请先通知
1. 相交链表(160)
1.1 暴力求解
1.1.1 分析
题目中描述既要判断是否相交,还要找交点。
把A链表中的所有节点依次在B中找一边。
为了防止在遍历链表时头节点丢失,先记录一下AB头节点:
struct ListNode* begin1 = headA;
struct ListNode* begin2 = headB;
先取A的节点,在B链表中遍历一遍,判断B中节点与A是否相交,如果相交,直接返回A的节点,如果不相交,B节点继续往后走。
当A的第一个节点在B中没有找到相交时,A节点就往后走,继续像第一个节点判断方式一样。不过这里得注意一下,再次访问B链表时候,B的走的节点又得从头节点开始begin2 = headB
。
当A链表中所有节点都访问完了后,B都没有与之相交的,就返回NULL
。
1.1.2 代码实现
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
struct ListNode* begin1 = headA;
struct ListNode* begin2 = headB;
while (begin1)
{
begin2 = headB;
while (begin2)
{
if (begin1 == begin2)
return begin1;
begin2 = begin2->next;
}
begin1 = begin1->next;
}
return NULL;
}
1.2 优化后求解
暴力求解虽然简单,但是时间复杂度太高为O(n^2),优化一下代码,使得时间复杂度到O(n)。
1.2.1 分析
可以先判断是否相交,如果A和B两个链表的尾节点的地址都相同,那么就A和B两个链表相交。如果如果A和B两个链表的尾节点的地址不相同,那么就A和B两个链表不相交。
如果相交那么交点怎么求呢?
先求出A和B两个链表的长度,
while(begin1->next)
{
lenA++;
begin1=begin1->next;
}
while(begin2->next)
{
lenB++;
begin2=begin2->next;
}
让长的链表先走两个链表相查的节点数,
while(n--)
{
longlist=longlist->next;
}
两个链表再同时走,第一个相同的就是交点。
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
1.2.2 代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode *begin1=headA;
struct ListNode *begin2=headB;
int lenA=1;
int lenB=1;
while(begin1->next)
{
lenA++;
begin1=begin1->next;
}
while(begin2->next)
{
lenB++;
begin2=begin2->next;
}
if(begin1!=begin2)
{
return NULL;
}
int n=abs(lenA-lenB);
struct ListNode *longlist=headA;
struct ListNode *shortlist=headB;
if(lenA<lenB)
{
longlist=headB;
shortlist=headA;
}
while(n--)
{
longlist=longlist->next;
}
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return longlist;
}
2. 随机链表的复制(138)
2.1 分析
这里链表里面包含单链表和随机指针,而随机指针指向链表任意节点或者为空。
对于节点的拷贝就是申请节点放原节点值任何尾插就行,复制链表倒是容易的。这里主要就是考虑随机指针怎么处理。
如果记录值让随机指针指向,可能会有多个相同的值。所以这里可以记录这个random出现的位置,看看是第几个用i记录,这样就不会出现多个随机指针指向同一个节点。如果每次复制节点都要找第i个,每个找random都是N,那么时间复杂度就是O(N^2)。时间复杂度太高了,优化一下。
第一步:可以把拷贝的节点都放在原节点的后面,也就是这样:
这样能方便找到原节点与random的关系。
while(cur)
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
copy->next=cur->next;
cur->next=copy;
cur=copy->next;
}
第二步:处理copy节点的random。
再从头开始走第二遍,copy节点每次都等于cur节点的next。
如果cur的random为空,copy节点的random也为空。
如果不是空,copy的random就是cur的random的next。
cur=head;
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
第三步:copy节点解下来尾插
出现申请一个新头节点,任何将copy节点一个一个取下来尾插,最后返回新的头节点。文章来源:https://www.toymoban.com/news/detail-805094.html
struct Node* newhead=NULL,*tail=NULL;
cur=head;
while(cur)
{
struct Node* copy=cur->next;
struct Node* next=copy->next;
if(tail==NULL)
{
newhead=tail=copy;
}
else
{
tail->next=copy;
tail=tail->next;
}
cur->next=next;
cur=next;
}
return newhead;
2.2 代码实现
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head;
while(cur)
{
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
copy->next=cur->next;
cur->next=copy;
cur=copy->next;
}
cur=head;
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
struct Node* newhead=NULL,*tail=NULL;
cur=head;
while(cur)
{
struct Node* copy=cur->next;
struct Node* next=copy->next;
if(tail==NULL)
{
newhead=tail=copy;
}
else
{
tail->next=copy;
tail=tail->next;
}
cur->next=next;
cur=next;
}
return newhead;
}
有问题请指出,大家一起进步!文章来源地址https://www.toymoban.com/news/detail-805094.html
到了这里,关于【OJ】链表刷题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!