160. Intersection of Two Linked Lists

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:

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. Credits: Special thanks to @stellari for adding this problem and creating all test cases.

/** * 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; int lenA = getLength(headA), lenB = getLength(headB); if (lenA > lenB) { for (int i = 0; i < lenA - lenB; ++i) headA = headA.next; } else { for (int i = 0; i < lenB - lenA; ++i) headB = headB.next; } while (headA != null && headB != null && headA != headB) { headA = headA.next; headB = headB.next; } return (headA != null && headB != null) ? headA : null; } public int getLength(ListNode head) { int cnt = 0; while (head != null) { ++cnt; head = head.next; } return cnt; }}

/** * 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) { int len_a = getListLen(headA), len_b = getListLen(headB); int diff = len_b - len_a; ListNode longer = diff>0? headB:headA; ListNode shorter = diff>0? headA:headB; for(int i=0; i

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */var getIntersectionNode = function(headA, headB) { if (headA === null || headB === null) { return null; } let pointer1 = headA; let pointer2 = headB; while (pointer1 !== pointer2) { pointer1 = pointer1.next; pointer2 = pointer2.next; if (pointer1 === pointer2) { return pointer1; } if (pointer1 === null) { pointer1 = headB; } if (pointer2 === null) { pointer2 = headA; } } return pointer1;};

/** * 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 a = headA; ListNode b = headB; boolean aSwapped = false; boolean bSwapped = false; while (a != null && b != null && a != b) { if (a == b) return a; if (a.next == null && !aSwapped) { aSwapped = true; a = headB; } else { a = a.next; // null if a has been swapped already } if (b.next == null && !bSwapped) { bSwapped = true; b = headA; } else { b = b.next; // null if b has been swapped already } } return null; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。