链表相关算法
程序员文章站
2024-03-22 18:33:28
...
1.链表反转
递归算法
ListNode* reverselist(ListNode *head)
{
if(head==NULL or head->next==NULL)
return head;
ListNode *p=reverselist(head->next);
head->next->next=head;
head=NULL;
return p;
}非递归算法
ListNode* reverselist(ListNode *head)
{
ListNode *cur=head;
if(cur==NULL)
return cur;
ListNode *pre=NULL;
while(cur!=NULL)
{
temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
2.单链表是否有环
bool hasCycle(ListNode *head)
{
if(head==NULL or head->next==NULL)
return false;
ListNode *fast,*slow;
slow=head;
fast=head->next;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return true;
}
return false;
}3.单链表找环入口
ListNode* detectCycle(ListNode *head)
{
if(head==NULL)
return head;
ListNode *fast,*slow;
slow=head;
fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
ListNode *slow2=head;
while(slow2!=slow)
{
slow=slow->next;
slow2=slow2->next;
}
return slow2;
}
}
return null;
}
4.单链表找交点
ListNode *getIntersectionNode(ListNode *headA,ListNode *headB)
{
ListNode *pa=headA;
ListNode *pb=headB;
while(pa!=pb)
{
pa=pa!=NULL?pa->next:headB;
pb=pb!=NULL?pb->next:headA;
}
return pa;
}5.链表找中间点
ListNode* middleNode(ListNode *head)
{
ListNode *slow=head;
ListNode *fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}6.已排序链表合并
ListNode *mergeTwoLists(ListNode *l1,ListNode *l2)
{
if(l1==NULL)
return l2;
if(l2==NULL)
return l1;
ListNode dummy(-1);
ListNode *p=&dummy;
for(;l1&&l2;p=p->next)
{
if(l1->val<l2->val)
{
p->next=l1;
l1=l1->next;
}
else
{
p->next=l2;
l2=l2->next;
}
}
p->next=l1!=NULL?l1:l2;
return dummy.next;
}