[Leetcode]160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

 

For example, the following two linked lists:

A: a1 → a2↘c1 → c2 → c3↗ B: b1 → b2 → b3

begin to intersect at node c1.

 

Notes:

/*** Definition for singly-linked list.* public 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 curA = headA,curB = headB;while (curA!=null&&curB!=null){if (curA.next ==null&&curB.next==null&&curA!=curB)return null; //如果走到了链的尽头，而这尽头又不是交//点，说明两条链不相交else if (curA==curB) //如果同时到交点了，就跳出循环break;if (curA.next == null) //下面这段可能需要画图理解curA = headB; //如果两条链有交点，则curA和curB到else //交点的距离是相同的curA = curA.next;if (curB.next == null)curB = headA;else curB = curB.next;}return curA;} }

 

• • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

转载于:https://www.cnblogs.com/David-Lin/p/7778509.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的[Leetcode]160. Intersection of Two Linked Lists的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。