汉中网站建设费用,手把手指导做网站,找网站有中文字目的,Wordpress修改主题菜单样式题目
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点#xff0c;返回 null 。 题目数据 保证 整个链式结构中不存在环。
思路
使用两个指针x,y同时遍历两个链表A和B。 当两个链表有相交节点时请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。 题目数据 保证 整个链式结构中不存在环。
思路
使用两个指针x,y同时遍历两个链表A和B。 当两个链表有相交节点时将链表分为两段 A ac B bc a和c为两个链表不同的节点c为两个链表共同的节点。 当x指针到达A链表末尾时让x指针指向B链表头。 当y指针到达B链表末尾时让y指针指向A链表头。 x指针的路程为acbc; y指针的路程为bcac; 两指针会在最后的c段路程相遇。
当两链表没有相交节点时两指针会分别走到两个链表的尾部。
代码
/*** 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 *preAheadA,*preBheadB;while(!(preANULLpreBNULL)){ if(preANULL){preAheadB;}if(preBNULL){preBheadA;}if(preApreB){return preB;}preApreA-next;preBpreB-next;}return NULL;}
};
