יול.14

למזג 2 רשימות מקושרות

למזג 2 רשימות מקושרות

נותנים 2 רשימות מקושרות שכל אחד מהן ממוינת. צריך למזג אותם ללא שימוש במבנים אחרים.

  1. public static LinkedList merge(LinkedList headOne, LinkedList headTwo) {
  2. LinkedList p1 = headOne;
  3. LinkedList p1Prev = null;
  4. LinkedList p2 = headTwo;
  5. while(p1 != null && p2 != null) {
  6. if(p1.value < p2.value) {
  7. p1Prev = p1;
  8. p1 = p1.next;
  9. } else {
  10. if(p1Prev != null)
  11. p1Prev.next = p2;
  12. p1Prev = p2;
  13. p2 = p2.next;
  14. p1Prev.next = p1;
  15. }
  16. }
  17. /*lets say:
  18. first list is 0
  19. second list is 1->2->3
  20. so we need fix now last pointer of first list to point to second pointer
  21. */
  22. if(p1 == null)
  23. p1Prev.next = p2;
  24. /* let's say in previous example, we need return first..*/
  25. return headOne.value < headTwo.value ? headOne : headTwo;
  26. }


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

תגובות(0)

השאירו תגובה

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

תגובה