我要评论
一.相交链表
相交：两个链表从头开始遍历，尾节点一定是同一个节点。
情况一：当两个链表长度相同时：
情况二：当两个链表长度不同时：
思路：
- 求两个链表长度的差值gap。
- 让长链表先走gap个节点。
- 分别遍历两个链表，比较是否为同一个节点，若是则相交，否则不相交。
代码如下：
typedef struct listnode listnode;
struct listnode *getintersectionnode(struct listnode *heada, struct listnode *headb)
{
listnode* la = heada;
listnode* lb = headb;
int lengtha = 0, lengthb = 0;
while(la)
{
lengtha++;//求链表a的长度
la = la->next;
}
while(lb)
{
lengthb++;//求链表b的长度
lb = lb->next;
}
//求链表a与链表b长度差的绝对值
int gap = abs(lengtha - lengthb);
//找出长链表与短链表
listnode* longlist = heada;
listnode* shortlist = headb;
if(lengthb > lengtha)
{
longlist = headb;
shortlist = heada;
}
//让长链表先走gap个节点
while(gap--)
{
longlist = longlist->next;
}
//此时longlist与shortlist指针在相对的位置上（同时遍历链表为null）
//判断两个链表是否相交
while(longlist && shortlist)
{
if(longlist == shortlist)
{
//链表相交
return longlist;
}
//两个指针继续往后走
longlist = longlist->next;
shortlist = shortlist->next;
}
//链表不相交
return null;
}
二.判断环型链表
思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！
因此，在带环链表中慢指针走一步，快指针走两步最终一定会相遇。
思考2：快指针一次走3步，走4步，…n步行吗?
思考：真的存在n是奇数，c是偶数这一条件？？？
下面给出等式：
代码如下：
- 慢指针一次走一步，快指针一次走两步
typedef struct listnode listnode;
bool hascycle(struct listnode* head)
{
listnode* slow = head;
listnode* fast = head;
while (fast && fast->next)
{
//慢指针一次走一步，快指针一次走两步
slow = slow->next;
fast = fast->next->next;
//当慢指针 == 快指针时，有环
if (slow == fast)
{
return true;
}
}
//无环
return false;
}
- 慢指针一次走一步，快指针一次走三步：
typedef struct listnode listnode;
bool hascycle(struct listnode *head)
{
listnode* slow = head;
listnode* fast = head;
while(fast && fast->next && fast->next->next)
{
//慢指针一次走一步，快指针一次走三步
slow = slow->next;
fast = fast->next->next->next;
//当慢指针 == 快指针时，有环
if(slow == fast)
{
return true;
}
}
//无环
return false;
}
三.求环型链表的入口节点
代码如下：
//解：快慢指针，快指针一次走两步，慢指针一次走一步,若为环型链表最终在环中相遇
// 然后让一个指针从相遇点开始走，一个指针从起点开始走，一次走一步，最终在进环处相遇
typedef struct listnode listnode;
struct listnode* detectcycle(struct listnode* head)
{
listnode* slow = head;
listnode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
//有环
listnode* meet = slow;//相遇点
while (meet != head)
{
//一个指针从相遇点开始走，一个指针从起点开始走，最终一定在入环点相遇
head = head->next;
meet = meet->next;
}
return meet;//入环点
}
}
return null;//无环
}
typedef struct listnode listnode;
struct listnode *getintersectionnode(struct listnode *heada, struct listnode *headb)
{
listnode* la = heada;
listnode* lb = headb;
int lengtha = 0, lengthb = 0;
while(la)
{
lengtha++;//求链表a的长度
la = la->next;
}
while(lb)
{
lengthb++;//求链表b的长度
lb = lb->next;
}
//求链表a与链表b长度差的绝对值
int gap = abs(lengtha - lengthb);
//找出长链表与短链表
listnode* longlist = heada;
listnode* shortlist = headb;
if(lengthb > lengtha)
{
longlist = headb;
shortlist = heada;
}
//让长链表先走gap个节点
while(gap--)
{
longlist = longlist->next;
}
//此时longlist与shortlist指针在相对的位置上（同时遍历链表为null）
//判断两个链表是否相交
while(longlist && shortlist)
{
if(longlist == shortlist)
{
//链表相交
return longlist;
}
//两个指针继续往后走
longlist = longlist->next;
shortlist = shortlist->next;
}
//链表不相交
return null;
}
struct listnode *detectcycle(struct listnode *head)
{
listnode* slow = head;
listnode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
//有环
listnode* meet = slow;//相遇点
listnode* newhead = meet->next;
meet->next = null;
return getintersectionnode(head, newhead);
}
}
return null;//无环
}
发表评论