LeetCode160.相交链表
问题描述方法一
算法思想动画演示代码演示算法分析 方法二
算法描述代码演示算法分析
LeetCode160.相交链表 问题描述给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
方法一 算法思想使用双指针
当两个链表headA和headB都不为null时,两个链表才可能相交,如果有一个链表为空,两个链表就不可能相交,所以首先应该判断两个链表是否为空,有一个为空,则返回null。
如果两个链表都不为空,则创建两个指针pA和pB, 初始时两个指针分别指向两个链表的头结点headA和headB,然后将两个指针分别遍历两个链表的每个结点。
具体步骤如下:
①每步 *** 作需要同时移动指针pA和pB。
②如果指针pA不为空,将指针更新到下一个结点;如果指针pB不为空,将指针更新到下一个结点。
③如果指针pA为空,则将指针pA移到链表headB的头结点;如果指针pB为空,则将指针pA移到链表headA;
④当指针pA和pB指向同一个结点或者都为null时,循环结束,返回他们指向的结点或者null。
class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; while(pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } }算法分析
时间复杂度 O(m + n),其中 m 和 n 分别是链表headA和headB的长度。两个指针同时遍历两个链表,每个链表各被遍历一次。
空间复杂度 O(1)。
同方法一也是采用双指针法。
当两个链表headA和headB有一个为null时,直接返回null。
如果两个链表都不为空,具体步骤如下:
①分别遍历两个链表,得到链表headA的长度count1,链表headB的长度count2。
②创建两个指针p1和p2,比较count1和count2,使指针p1指向较长的链表,指针p2指向较短的链表。
③计算两个链表的长度差diff,然后让指针p1先往后遍历diff个结点。
④同时移动指针p1和p2。当指针p1和p2指向同一个结点或者都为null时,循环结束,返回他们指向的结点或者null。
class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA == null || headB == null) { return null; } ListNode p1; ListNode p2; int count1 = 0; int count2 = 0; for(ListNode p = headA; p != null;p = p.next) { count1++; } for(ListNode p = headB; p != null;p = p.next) { count2++; } p1 = count1 > count2 ? headA : headB; p2 = count1 > count2 ? headB : headA; int diff = Math.abs(count1 - count2); while(diff-- > 0) { p1 = p1.next; } while(p1 != p2) { p1 = p1.next; p2 = p2.next; } return p1; } }算法分析
时间复杂度 O(m + n),其中 m 和 n 分别是链表headA和headB的长度。两个指针同时遍历两个链表,每个链表各被遍历一次。
空间复杂度 O(1)。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)