21. Merge Two Sorted Lists

مسئله: ادغام دو لیست مرتب پیوندی

فرض کنید head های دو لیست پیوندی مرتب list1 و list2 به شما داده شده است.

وظیفه شما این است که این دو لیست را در یک لیست مرتب ادغام کنید. لیست نهایی باید با اتصال گره‌های دو لیست اولیه ساخته شود.

خروجی: head (اولین گره) لیست پیوندی ادغام شده را برگردانید.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

 قیدها

• اتعداد گره‌ها در هر دو لیست در محدوده [۰، ۵۰] قرار دارد.
• -۱۰۰ ≤ Node.val ≤ ۱۰۰
• هر دو لیست list1 و list2 به ترتیب غیرنزولی مرتب شده‌اند.

راه‌حل‌ها

راه‌حل ۱: بازگشتی (Recursion)

ابتدا بررسی می کنیم که آیا لیست های پیوندی l_1 و l_2 خالی هستند یا خیر. اگر یکی از آنها خالی باشد، لیست دیگر را برمی‌گرداندیم. در غیر این صورت، گره های سر (head) l_1 و l_2 را مقایسه می کنیم:

• اگر مقدار گره سر l_1 کمتر یا مساوی مقدار گره سر l_2 باشد، به طور بازگشتی تابع mergeTwoLists(l_1.next, l_2) را فراخوانی کرده و گره سر l_1 را به گره سر لیست برگشتی متصل می کنیم و گره سر l_1 را برمی‌گردانیم.
• در غیر این صورت، به طور بازگشتی تابع mergeTwoLists(l_1, l_2.next) را فراخوانی کرده و گره سر l_2 را به گره سر لیست برگشتی متصل می کنیم و گره سر l_2 را برمی گردانیم.

پیچیدگی زمانی این الگوریتم O(m+n) و پیچیدگی فضایی آن O(m+n) است. در اینجا، m و n به ترتیب طول های دو لیست پیوندی هستند.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
 if list1 == nil {
  return list2
 }
 if list2 == nil {
  return list1
 }
 if list1.Val <= list2.Val {
  list1.Next = mergeTwoLists(list1.Next, list2)
  return list1
 } else {
  list2.Next = mergeTwoLists(list1, list2.Next)
  return list2
 }
}

راه حل ۲: Iteration

همچنین می‌توانیم از تکرار (iteration) برای ادغام دو لیست پیوسته مرتب استفاده کنیم.

ابتدا یک گره سر (head) صوری (dummy) تعریف می‌کنیم، سپس حلقه‌ای روی دو لیست پیوسته اجرا می‌کنیم، گره‌های سر هر دو لیست را باهم مقایسه می‌کنیم، گره کوچکتر را به انتهای dummy اضافه می‌کنیم تا زمانی که یکی از لیست‌های پیوسته خالی شود. سپس بخش باقی مانده از لیست دیگر را به انتهای dummy اضافه می‌کنیم.

در نهایت، dummy.next را برمی‌گردانیم.

پیچیدگی زمانی این الگوریتم O(m+n) است، که در آن m و n به ترتیب طول دو لیست پیوسته هستند. با صرفنظر از فضای مصرف شده توسط لیست پیوسته خروجی، پیچیدگی فضایی این الگوریتم O(1) است.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
 dummy := &ListNode{}
 curr := dummy
 for list1 != nil && list2 != nil {
  if list1.Val <= list2.Val {
   curr.Next = list1
   list1 = list1.Next
  } else {
   curr.Next = list2
   list2 = list2.Next
  }
  curr = curr.Next
 }
 if list1 != nil {
  curr.Next = list1
 } else {
  curr.Next = list2
 }
 return dummy.Next
}