SpringBoot怎么找出两个单链表的交叉节点

发布时间:2021-12-18 15:49:06 作者:iii
来源:亿速云 阅读:150

这篇文章主要讲解了“SpringBoot怎么找出两个单链表的交叉节点”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“SpringBoot怎么找出两个单链表的交叉节点”吧!

题目:写一个程序找出两个单链表的交叉节点。
思路:单链表A和单链表B,交叉点后的部分是一样的,也就是说长度是一样的,如上所示:c1 → c2 → c3。所以,将单链表A和单链表B相差的部分去掉,依次对应比较等长的部分即可。在计算两个链表的长度之后,比较两个链表的尾节点是否一样,如果不一样说明没有交叉节点,返回NULL。

Language : c

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *curA = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode *curB = (struct ListNode*)malloc(sizeof(struct ListNode));
    curA = headA;
    curB = headB;int length_a = 1;int length_b = 1;int i = 0;if(curA == NULL || curB == NULL){return NULL;
    }while(curA->next != NULL){
        curA = curA->next;
        length_a++;
    }while(curB->next != NULL){
        curB = curB->next;
        length_b++;
    }if(curA != curB){return NULL;
    }
    curA = headA;
    curB = headB;if(length_a > length_b){for(i; i < length_a-length_b; i++){
            curA = curA->next;
        }
        i = 0;
    }else if(length_a < length_b){for(i; i < length_b-length_a; i++){
            curB = curB->next;
        }
        i = 0;
    }while(curA != curB){
        curA = curA->next;
        curB = curB->next;
    }return curA;
}

Language : cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * }; */class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA, *curB;
        curA = headA;
        curB = headB;if(curA == NULL || curB == NULL){return NULL;
        }int length_a = getLength(curA);int length_b = getLength(curB);if(length_a > length_b){for(int i=0; i < length_a-length_b; i++){
                curA = curA->next;
            }
        }else if(length_a < length_b){for(int i=0; i < length_b-length_a; i++){
                curB = curB->next;
            }
        }while(curA != curB){
            curA = curA->next;
            curB = curB->next;
        }return curA;
    }
private:int getLength(ListNode *head){int length = 1;while(head->next != NULL){
            head = head->next;length++;
        }return length;
    }
};

Language:python

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):def getIntersectionNode(self, headA, headB):"""
        :type head1, head1: ListNode
        :rtype: ListNode
        """if headA is None or headB is None:return Nonepa = headA # 2 pointerspb = headBwhile pa is not pb:# pa先遍历headA,然后再遍历headB# pb先遍历headB,然后再遍历headApa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.nextreturn pa # 只有两种方式结束循环,一种是pa和pb所指相同,另一种是headA和headB都已经遍历完仍然没有找到。

感谢各位的阅读,以上就是“SpringBoot怎么找出两个单链表的交叉节点”的内容了,经过本文的学习后,相信大家对SpringBoot怎么找出两个单链表的交叉节点这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

推荐阅读:
  1. LeetCode如何找出链表的中间节点
  2. 单链表一[带头节点链表]

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

springboot

上一篇:GoogleEarth如何实现动态大小、鼠标消息、截图

下一篇:如何进行springboot配置templates直接访问的实现

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》