ינו.29

נקודת מפגש של שתי רשימות מקושרות

נקודת מפגש של שתי רשימות מקושרות

יש למצוא נקודת מפגש שלי 2 רשימות מקושרות

  1. //solution 1
  2. public Node getIntersection(Node headA, Node headB) {
  3. if(headA == null || headB == null) return null;
  4. Node a_pointer = headA;
  5. Node b_pointer = headB;
  6. while(a_pointer != b_pointer) {
  7. if(a_pointer == null)
  8. a_pointer = headB;
  9. else
  10. a_pointer = a_pointer.next;
  11. if(b_pointer == null)
  12. b_pointer = headA;
  13. else
  14. b_pointer = b_pointer.next;
  15. }
  16. return a_pointer;
  17. }
  18.  
  19. //solution 2
  20. int getNodesCount(Node node)
  21. {
  22. Node current = node;
  23. int count = 0;
  24.  
  25. while (current != null)
  26. {
  27. count++;
  28. current = current.next;
  29. }
  30. return count;
  31. }
  32.  
  33. int getNode(Node head1, Node head2)
  34. {
  35. int c1 = getNodesCount(head1);
  36. int c2 = getNodesCount(head2);
  37. int d;
  38.  
  39. if (c1 > c2)
  40. {
  41. d = c1 - c2;
  42. return getIntesectionNode(d, head1, head2);
  43. }
  44. else
  45. {
  46. d = c2 - c1;
  47. return getIntesectionNode(d, head2, head1);
  48. }
  49. }
  50.  
  51. int getIntesectionNode(int d, Node node1, Node node2)
  52. {
  53. int i;
  54. Node current1 = node1;
  55. Node current2 = node2;
  56. for (i = 0; i < d; i++)
  57. {
  58. if (current1 == null)
  59. {
  60. return -1;
  61. }
  62. current1 = current1.next;
  63. }
  64. while (current1 != null && current2 != null)
  65. {
  66. if (current1.data == current2.data)
  67. {
  68. return current1.data;
  69. }
  70. current1 = current1.next;
  71. current2 = current2.next;
  72. }
  73. return -1;
  74. }


תגיות:
שתף את הסיפור הזה:

תגובות(0)

השאירו תגובה

קפטצ'ה לא מתאימה

תגובה