สร้างรายการเชื่อมโยงรวมสูงสุดจากสองรายการที่เชื่อมโยงที่เรียงลำดับซึ่งมีโหนดทั่วไปบางส่วนในPython

สมมติว่าเรามีรายการที่เชื่อมโยงที่เรียงลำดับแล้วสองรายการ เราจะต้องสร้างรายการที่เชื่อมโยงที่ประกอบด้วยเส้นทางรวมที่ใหญ่ที่สุดจากโหนดเริ่มต้นไปยังโหนดปลาย รายการสุดท้ายอาจประกอบด้วยโหนดจากรายการอินพุตทั้งสอง

เมื่อเราสร้างรายการผลลัพธ์ เราอาจสลับไปยังรายการอินพุตอื่นสำหรับจุดตัดเท่านั้น (สองโหนดที่มีค่าเท่ากันในรายการ) เราต้องแก้โดยใช้พื้นที่เพิ่มเติมคงที่

ดังนั้น หากอินพุตเป็น [6,8,35,95,115,125], [5,8,17,37,95,105,125,135] ผลลัพธ์จะเป็น [6,8,17,37,95,115,125,135]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ผลลัพธ์ :=ไม่มี

• Previous1 :=a, ปัจจุบัน1 :=a

• Previous2 :=b, ปัจจุบัน2 :=b

• ในขณะที่ current1 ไม่เหมือนกับ none หรือ current2 ไม่เหมือนกับ none ให้ทำ

  • res1 :=0, res2 :=0

  • ในขณะที่ current1 และ current2 ไม่เป็นโมฆะ และข้อมูลของ current1 ไม่เหมือนกับข้อมูลของ current2 ให้ทำ

    • ถ้า data ของ current1

      • res1 :=res1 + ข้อมูลปัจจุบัน1

      • ปัจจุบัน1 :=ถัดไปของปัจจุบัน1

    • มิฉะนั้น

      • res2 :=res2 + ข้อมูลปัจจุบัน2

      • ปัจจุบัน2 :=ถัดไปของปัจจุบัน2

  • ถ้า current1 เป็นโมฆะ แล้ว

    • ในขณะที่ current2 ไม่เป็นโมฆะ ให้ทำ

      • res2 :=res2 + ข้อมูลปัจจุบัน2

      • ปัจจุบัน2 :=ถัดไปของปัจจุบัน2

  • ถ้า current2 เป็นโมฆะ แล้ว

    • ในขณะที่ current1 ไม่เป็นโมฆะให้ทำ

      • res1 :=res1 + ข้อมูลปัจจุบัน1

      • ปัจจุบัน1 :=ถัดไปของปัจจุบัน1

  • ถ้า Previous1 เหมือนกับ a และ Previous2 เหมือนกับ b แล้ว

    • ผลลัพธ์ :=ก่อนหน้า1 เมื่อ (res1> res2) มิฉะนั้น ก่อนหน้า2

  • มิฉะนั้น

    • ถ้า res1> res2 แล้ว

      • next of Previous2 :=next of Previous1

    • มิฉะนั้น

      • next of Previous1 :=next of Previous2

  • Previous1 :=ปัจจุบัน1

  • Previous2 :=ปัจจุบัน2

  • ถ้า current1 ไม่เป็นโมฆะ

    • ปัจจุบัน1 :=ถัดไปของปัจจุบัน1

  • ถ้า current2 ไม่เป็นโมฆะ

    • ปัจจุบัน2 :=ถัดไปของปัจจุบัน2

• แสดงเนื้อหาของผลลัพธ์

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class LinkedList(object):
   def __init__(self, data_set = []):
      self.head = None
      if len(data_set) > 0:
         for item in data_set:
            self.insert_node(item)
   class ListNode(object):
      def __init__(self, d):
         self.data = d
         self.next = None
   def insert_node(self, new_data):
      new_node = self.ListNode(new_data)
      new_node.next = self.head
      self.head = new_node
   def find_max_sum_list(self, a, b):
      result = None
      previous1 = a
      current1 = a
      previous2 = b
      current2 = b
      while current1 != None or current2 != None:
         res1 = 0
         res2 = 0
         while current1 != None and current2 != None and current1.data != current2.data:
            if current1.data < current2.data:
               res1 += current1.data
               current1 = current1.next
            else:
               res2 += current2.data
               current2 = current2.next
         if current1 == None:
            while current2 != None:
               res2 += current2.data
               current2 = current2.next
         if current2 == None:
            while current1 != None:
               res1 += current1.data
               current1 = current1.next
         if previous1 == a and previous2 == b:
            result = previous1 if (res1 > res2) else previous2
         else:
            if res1 > res2:
               previous2.next = previous1.next
            else:
               previous1.next = previous2.next
         previous1 = current1
         previous2 = current2
         if current1 != None:
            current1 = current1.next
         if current2 != None:
            current2 = current2.next
      while result != None:
         print(result.data, end = ' ')
         result = result.next
my_list1 = LinkedList([125,115,95,35,8,6])
my_list2 = LinkedList([135,125,105,95,37,17,8,5])
my_list1.find_max_sum_list(my_list1.head, my_list2.head)

อินพุต

[125,115,95,35,8,6], [135,125,105,95,37,17,8,5]

ผลลัพธ์

6 8 17 37 95 115 125 135