链表OJ题
一.相交链表
相交链表
相交:两个链表从头开始遍历,尾节点一定是同一个节点。
情况一:当两个链表长度相同时:
情况二:当两个链表长度不同时:
思路:
- 求两个链表长度的差值gap。
- 让长链表先走gap个节点。
- 分别遍历两个链表,比较是否为同一个节点,若是则相交,否则不相交。
代码如下:
typedefstructListNode ListNode;structListNode*getIntersectionNode(structListNode*headA,structListNode*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;}//链表不相交returnNULL;}
二.判断环型链表
环型链表
思路:快慢指针,即慢指针一次⾛一步,快指针一次走两步,两个指针从链表起始位置开始行,如果链表带环则一定会在环中相遇,否则快指针率先走到链表的未尾。
思考1
:为什么快指针每次走两步,慢指针走一步可以相遇,有没有可能遇不上,请推理证明!
因此,在带环链表中慢指针走一步,快指针走两步最终一定会相遇。
思考2
:快指针一次走3步,走4步,…n步行吗?
思考:真的存在N是奇数,C是偶数这一条件???
下面给出等式:
代码如下:
- 慢指针一次走一步,快指针一次走两步
typedefstructListNode ListNode;
bool hasCycle(structListNode* 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;}
- 慢指针一次走一步,快指针一次走三步:
typedefstructListNode ListNode;
bool hasCycle(structListNode*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;}
三.求环型链表的入口节点
环型链表 ||
思路:快慢指针,快指针一次走两步,慢指针一次走一步,若为环型链表最终在环中相遇,然后让一个指针从相遇点开始走,一个指针从起点开始走,一次走一步,最终在进环处相遇。
代码如下:
//解:快慢指针,快指针一次走两步,慢指针一次走一步,若为环型链表最终在环中相遇// 然后让一个指针从相遇点开始走,一个指针从起点开始走,一次走一步,最终在进环处相遇typedefstructListNode ListNode;structListNode*detectCycle(structListNode* 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;//入环点}}returnNULL;//无环}
typedefstructListNode ListNode;structListNode*getIntersectionNode(structListNode*headA,structListNode*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;}//链表不相交returnNULL;}structListNode*detectCycle(structListNode*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;returngetIntersectionNode(head, newHead);}}returnNULL;//无环}
版权归原作者 清风~徐~来 所有, 如有侵权,请联系我们删除。