从零开始算法之路 ----相交链表

淩亂°似流年 2022-01-28 15:51 252阅读 0赞

前言：小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（[https://leetcode-cn.com/problems/intersection-of-two-linked-lists/][https_leetcode-cn.com_problems_intersection-of-two-linked-lists]）

题目描述：

编写一个程序，找到两个单链表相交的起始节点。（题目详情请点链接）

解决方案：

思路：用第一个链表的每一个节点和第二个链表的每一个节点对比，判断是否相交。时间复杂度：O(n\*m) 【n为第一个链表长度，m为第二个链表长度】

代码如下：

/**
     * 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) {
            //如果链表为空相交节点为空 
        	if(headA == NULL || headB == NULL)
        	    return NULL;
        	ListNode *first = headA;
        	ListNode *second = headB;
            
            //第一个循环遍历第一个链表
        	while(first != NULL && second != NULL ){ 
                   //第二个循环遍历第二个链表，并判断两链表是否相交
    	    	while(first != NULL && second != NULL ){
                    //如果链表相交则返回相交节点
    	    		if(first == second)
    	    		    return first;	    	
    	    		second = second->next;	    		
    			}
    			first = first->next;
                //每次第二个链表遍历过一遍，让second = headB，重新开始遍历第二个链表
                second = headB;
    		}
    	
    		//如果两个链表没有相交则返回空（相交节点为空） 
    		return NULL;   	
        }
    };

[https_leetcode-cn.com_problems_intersection-of-two-linked-lists]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/