leetcode 面试题 02.07 链表相交

简介: leetcode 面试题 02.07 链表相交

面试题02.07链表相交


71b268c3af274797a7cbaf51cdf4517f.png

暴力循环

两层循环,分别循环两个链表

/**
 * 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 *dummy_a = new ListNode(0,NULL);
        ListNode *dummy_b = new ListNode(0,NULL);
        ListNode *temp, *tempA , *tempB;
        int flag = 0;
        dummy_a->next = headA;
        dummy_b->next = headB;
        tempA = dummy_a;
        tempB = dummy_b;
        if(headA == headB) return headA;
        while(tempA->next != NULL)
        {
            while(tempB->next != NULL)
            {
                if(tempA == tempB)
                {
                    return tempA; 
                }
                tempB = tempB->next;
            }
            tempB = dummy_b;
            tempA = tempA->next;
        }
        while(dummy_b)
        {
            if(tempA == dummy_b)return tempA;
            dummy_b = dummy_b->next;
        }
         while(dummy_a)
        {
            if(tempB == dummy_a)return tempB;
            dummy_a = dummy_a->next;
        }
        return NULL;
    }
};


对其相同部分

先计算两个链表的长度,因为后面完全一致,让长的链表先向后移动到和短链表相同长度。再依次查找是否完全一致的节点。

/**
 * 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) {
        int length_A = 0 , length_B = 0 ,diff=0 ;
        ListNode *cur_A = headA , *cur_B = headB;
        ListNode *dummy_a = new ListNode(0);
        ListNode *dummy_b = new ListNode(0);
        dummy_a->next = headA;
        dummy_b->next = headB;
        while(dummy_a->next != NULL)
        {
            length_A++;
            dummy_a = dummy_a->next;
        }
        while(dummy_b->next != NULL)
        {
            length_B++;
            dummy_b = dummy_b->next;
        }
        if(length_A >= length_B)
        {
            for(int i =0;i< length_A-length_B;i++)
            {
                cur_A = cur_A->next;
            }
        }else
        {
            for(int i =0;i< length_B-length_A;i++)
            {
                cur_B = cur_B->next;
            }
        }
        while(cur_A != cur_B)
        {
            cur_A = cur_A->next;
            cur_B = cur_B->next;
        }
        return cur_A;
    }
};


二刷

/**
 * 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;
        int numA = 0 ,numB = 0 , diff =0;
        ListNode *cur_A = headA;
        ListNode *cur_B = headB;
        while(cur_A != NULL)
        {
            cur_A = cur_A->next;
            numA++ ;
        }
        while(cur_B != NULL)
        {
            cur_B = cur_B->next;
            numB++ ;
        }
        cur_A = headA;
        cur_B = headB;
        if(numA > numB)
        {
            diff = numA -numB;
            while(diff--)
                cur_A = cur_A->next;
        }else if(numA < numB)
        {
            diff = numB - numA;
            while(diff--)
                cur_B = cur_B->next;
        }
        // cout<<cur_A->val<<' '<<cur_B->val;
        while(cur_A != NULL)
        {
            if(cur_A == cur_B)
                return cur_A;
            cur_A = cur_A->next;
            cur_B = cur_B->next;
        }
        return NULL;
    }
};


相关文章
|
10天前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
23 1
|
17天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
41 0
Leetcode第21题(合并两个有序链表)
|
17天前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
13 0
LeetCode第二十四题(两两交换链表中的节点)
|
17天前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
36 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
14天前
|
存储 算法 安全
HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环
HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环
|
17天前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
39 0
|
17天前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
17 0
|
17天前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
13 0
|
17天前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
12 0
|
17天前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
27 0