10.2 רשימה מקושרת ורקורסיה הרצאה

רשימה מקושרת

• רשימה מקושרת הוא מבנה נתונים מיוחד, שמכיל רשימה של חוליות (node-ים), כל חוליה מחזיקה ערך מסויים (למשל מספר) ומצביעה על חולייה אחרת.
  דוגמה להגדרה של רשימת חולית (רשימה מקושרת)
  

  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None
  
  n1 = Node(5)
  n2 = Node(3)
  n3 = Node(4)
  n1.next = n2
  n2.next = n3
  

שאלה מודרכת: Intersection of Two Linked list (השאלה לקוחה מleetcode)

קיימים שני רשימות מקושורת, A ו-B: ידוע שהם מתלקדים בנקודה בחוליה מסויימת, מצאו אותה והחזירו את הערך שלה.

- אם לא מצאתם חוליה שמקשרת בניהם, החזירו None.
דוגמה:
- נתון הlinked list הבא:

- הפונקציה אמורה להחזיר 8.
- נתון הlinked list הבא:

- הפונקציה אמורה להחזיר 2.
- נתון הlinked list הבא:

- הפונקציה אמורה להחזיר None

פתרון brute force:
אפשר לעבור על כל השני הרשימות המקושרות עם שני לולאות, ולחפש את הnode הזהה.

def get_intersection(Node head_a, Node head_b):
    while head_a is not None:
        while head_b is not None:
            if head_a == head_b:
                return head_a
            head_b = head_b.next
        head_a = head_a.next

אם האורך של הרשימה מקושרת A הוא n, ואורך של הרשימה המקושרת הוא m, הtime complexity יהיה O(m*n).

פתרון set:
במקום לעבור עם לולאה מקוננת (לולאה בתוך לולאה) על כל הרשימות המקושרות, אנחנו יכולים לעבור על רשימה אחת, ולרשום את כל הערכים שלה בתוך set: אחד הדברים שחשובים שכדאי לכם להכיר על set, הוא שהtime complexity של חיפוש ערך מסויים בset הוא o(1), כך שאחרי שנמלא את כל הערכים של רשימה מסויימת בset עם לולאה (O(n)) נוכל לגשת לכל הערכים שלה בO(1).
אחרי שיהיה לנו set כזה, נעבור על הרשימה המקושרת השנייה ונבדוק האם הערכים שלה מופיעים בset.

def get_intersection(Node head_a, Node head_b):
    my_set = {}
    while head_a is not None:
        my_set.add(head_a)
        head_a = head_a.next

    while head_b is not None:
        if head_b in my_set:
            return head_b
        head_b = head_b.next

    return None

- אם האורך של הרשימה מקושרת A הוא n, ואורך של הרשימה המקושרת הוא m, הtime complexity יהיה O(m+n). והspace complexity יהיה O(n)

פתרון two pointers:
בוא נקח כדוגמה את התמונה הבאה:

הסיבה שכל כך קשה לנו למצוא מתי הרשימות נפגשות כי אנחנו לא יודעים כמה חוליות אנחנו צריכים לעבור בכל רשימה כדי להגיע לחוליה המשותפת, יכול להיות שבA, יהיו 2 חוליות לפני המפגש ויכול להיות שבB יהיה 3 חוליות לפני המפגש. למעשה בגלל שכמות החוליות שיכולה להיות לפני המפגש של הרשימות היא שונה, קשה לנו למצוא את החוליה של הפגישה בניהם.
- אז, אם אנחנו נדע בדיוק מה האורך של שני הרשימות המקושרת, אנחנו נוכל לחשב כמה חוליות אנחנו צריכים לשלול בהתחלה כדי שכמות החוליות לפני המפגש תהיה זהה, ויהיה לנו קל יותר למצוא את החולית מפגש.
1. קודם נעבור על הרשימות עם לולאה אחת לכל רשימה כדי לחשב את אורכן.
2. אם מצאנו שקיימת רשימה ארוכה יותר מהשניה, נמחק את החוליות הראשונות שלה (על פי כמה שהיא יותר ארוכה)
3. ואז נעבור עם שני מצביעים בלולאה אחת על שני הרשימות, ואם נמצא נקודת מפגש - נחזיר אותה, אם לא נחזיר None

def get_intersection(Node head_a, Node head_b):
    l_a, l_b = head_a, head_b
    len_a, len_b = 0, 0
    # Calculate lists lengths
    while l_a is not None:
        l_a = l_a.next
        len_a+=1

    while l_b is not None:
        l_b = l_b.next
        len_b+=1

    # Adjust pointers 
    l_a, l_b = head_a, head_b
    while len_a > len_b:
        l_a = l_a.next
        len_a-=1

    while len_b > len_a:
        l_b = l_b.next
        len_b-=1

    # finding intersection
    while l_a != l_b:
        l_a = l_a.next
        l_b = l_b.next

    return l_a

- אם האורך של הרשימה מקושרת A הוא n, ואורך של הרשימה המקושרת הוא m, הtime complexity יהיה O(m+n). והspace complexity יהיה O(1).

רקורסיה

• רקורסיה היא פונקציה שקוראת לעצמה.
  דוגמה: סדרת פיבונצ'י היא סדרת מספרים שמתחילה ב0,1 ומקיימת חוק שבו כל איבר ברשימה הוא סכום של שני האיברים הקודמים לו:
  

  0, 1, 1, 2, 3, 5, 8, 13, 21, 34
  

• באמצעות רקורסיה נוכל לכתוב פונקציה שכאשר נביא לה מספר, היא תחזיר לנו את המספר בסדרת פיבונצ'י,
  

  def fib(n):  
      if n == 0:  
          return 0  
      if n == 1:  
          return 1  
  
      return fib(n-1) + fib(n-2)
  

• אם n שאנחנו מקבלים הוא 0, אנחנו מחזירים 0, ואם 1 אז אנחנו מחזירים 1, אחרת אנחנו קוראים לfib שוב, הפעם עם n-1 + n-2.
• רקורסיה זה סוג של לולאה, שכל קריאה בלולאה קוראת באצעות קריאה לאותו פונקציה, למשל במקרה הזה כאשר אנחנו קוראים לfib שוב ושוב.
• מבחינת מהירות ומקום, תמיד עדיף להשתמש בלולאה מאשר רקורסיה: באלגוריתמיקה לפעמים נשתמש ברקורסיה לפעמים כדי לכתוב קוד נקי יותר, קיימים המון אלגוריתמים שבהם נשתמש ברקורסיה מהבחירה הזו.

חזרה

• רשימה מקושרת וחוליות
• שאלת intersection of two linked list
• איך set יכול לעזור לנו לפתור בעיה בדומה למילון.
• רקורסיה.

תרגול

• המשיכו לעשות המון leetcode בעצמכם! לא מצליחים? הכל טוב, תקראו את הפתרונות באינטרנט. המשיכו עד שתשתפרו.