تسلط بر لیست پیوندی: شکستن مشکلات LeetCode در لیست

Summarize this content to 400 words in Persian Lang
سلام 👋🏻، می دانم که مدتی از شروع این سفر می گذرد و می خواهم باور کنم که سفر فوق العاده ای بوده است! 🚀

امروز، ما برخی از رایج ترین مشکلات لیست پیوندی در LeetCode را حل خواهیم کرد. 🧩 ایده این است که شما را با مفهوم لیست های پیوندی و نحوه حل مشکلات موجود در آنها آشنا کنیم. 💡 مشکلاتی که ما با آنها مقابله خواهیم کرد انواع مختلفی از لیست های مرتبط را شامل می شود، با دشواری از آسان تا سخت، که همه آنها گام به گام بررسی می شوند. 📈 بنابراین، اگر این سریال را دنبال کرده اید، پس خوب است که بروید! 🎉 اگر نه، ممکن است بخواهید مقالات قبلی این مجموعه را بررسی کنید تا به این موضوع پی ببرید. 📚

طرح کلی دوره

مقدمه
فهرست پیوندی رویکرد حل مسئله

مشکلات لیست تک پیوندی

نتیجه گیری

مقدمه

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

فهرست پیوندی رویکرد حل مسئله

وقتی نوبت به حل مشکلات لیست پیوندی می رسد، مراحل خاصی وجود دارد که می توانیم برای اطمینان از دریافت پاسخ صحیح دنبال کنیم. این مراحل عبارتند از:

مشکل را درک کنید:

بیانیه مشکل را با دقت بخوانید.
ورودی و خروجی را شناسایی کنید.
هر گونه فرض یا محدودیت را روشن کنید.

موارد لبه را در نظر بگیرید:

به این فکر کنید که اگر لیست پیوندی خالی باشد چه اتفاقی می افتد.
موردی را در نظر بگیرید که در آن لیست پیوندی فقط یک گره (سر) دارد.

راه حل را برنامه ریزی کنید:

در مورد مراحل مورد نیاز برای حل مشکل فکر کنید.
استفاده از اشاره گر یا تکرار را برای عبور از لیست پیوندی (در صورت نیاز) در نظر بگیرید.
استفاده از یک گره ساختگی را برای ساده کردن موارد لبه (در صورت نیاز) در نظر بگیرید.

پیاده سازی راه حل:

کد را برای حل مشکل بنویسید.

تست راه حل:

راه حل را با ورودی های مختلف تست کنید تا مطمئن شوید که درست کار می کند.
موارد لبه ای که در نظر گرفته نشده اند را بررسی کنید.

بهینه سازی راه حل:

پیچیدگی زمانی راه حل را در نظر بگیرید.
به دنبال راه هایی برای بهبود راه حل باشید (مثلاً با استفاده از یک الگوریتم سریعتر).

متأسفانه، ما در این مقاله با پیچیدگی زمانی راه حل سروکار نخواهیم داشت زیرا بیشتر به مفهوم و نحوه حل مشکل می پردازیم.

مشکلات لیست تک پیوندی

در این بخش، ما فقط دو مورد از رایج ترین مشکلات لیست تک پیوندی در leetcode را حل خواهیم کرد. آنها عبارتند از: فهرست پیوند معکوس و ادغام دو فهرست مرتب شده

سوال 1: لیست پیوندی معکوس

با توجه به head از یک لیست پیوندی منفرد، لیست را معکوس کنید و لیست معکوس شده را برگردانید.

مثال 1:ورودی: سر = [1,2,3,4,5]خروجی: [5,4,3,2,1]

مثال 2: > > ورودی: سر = [1,2] > خروجی: [2,1]

رویکرد

از آنجایی که ما با یک لیست پیوندی منفرد سر و کار داریم، این بدان معناست که تنها یک داده و یک اشاره گر به گره بعدی در یک گره واحد وجود دارد. از آنجایی که نمی‌توانیم لیست را به صورت معکوس طی کنیم، باید جهت لیست را برعکس کنیم. ما می توانیم این کار را به سادگی با تغییر جهت اشاره گر بعدی هر گره انجام دهیم.

پیاده سازی راه حل

/** Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/

function reverseList(head) {
if (!head) return null;
if (!head.next) return head;
let node = null;
while (head) {
let currentNode = head.next;
head.next = node;
node = head;
head = currentNode;
}
return node;
}

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

سوال 2: گره نهم را از انتهای لیست حذف کنید

با توجه به head از یک لیست پیوندی، آن را حذف کنید nth از انتهای لیست گره بزنید و سر آن را برگردانید.

مثال 1: > > ورودی: سر = [1,2,3,4,5]، n = 2خروجی: [1,2,3,5]

مثال 2: > ورودی: سر = [1]، n = 1خروجی: []

رویکرد

از دو نشانگر استفاده کنید: یک اشاره گر سریع و یک اشاره گر آهسته.
نشانگر سریع n گره را به جلو حرکت دهید.
هر دو نشانگر را حرکت دهید تا نشانگر سریع به پایان برسد.
نشانگر آهسته اکنون در گره قبل از حذف قرار می گیرد.
برای رد شدن از گره n، اشاره گر بعدی اشاره گر کند را به روز کنید.
سر لیست اصلاح شده را برگردانید.

پیاده سازی راه حل

const removeNthFromEnd = function (head, n) {
// Create a dummy node to handle edge cases (e.g., removing the head)
const newNode = new ListNode(0);
newNode.next = head;
let first = newNode;
let second = newNode;

// Move the first pointer n+1 steps ahead
for (let i = 0; i <= n; i++) {
first = first.next;
}

// Move both pointers until the first pointer reaches the end
while (first !== null) {
first = first.next;
second = second.next;
}

// Remove the nth node by updating the next pointer
second.next = second.next.next;

// Return the head of the modified list (excluding the dummy node)
return newNode.next;
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

نتیجه گیری

در این مقاله، برخی از رایج ترین مشکلات لیست پیوندی در LeetCode را حل کرده ایم. ما با مشکل لیست پیوند معکوس شروع کردیم و سپس به سمت حذف nامین گره از مشکل انتهای لیست حرکت کردیم. ما دیده ایم که چگونه به این مشکلات نزدیک شویم و چگونه آنها را گام به گام حل کنیم 🚶‍♂️👣.

به یاد داشته باشید که تمرین کلید تسلط بر مشکلات لیست پیوندی است. در اینجا یک مجموعه مشکلات لیست پیوندی در LeetCode حاوی حدود 75 مشکل از آسان تا سخت است.

بعدی… ما به ساختارهای داده صف و پشته می پردازیم! 🏊‍♂️🔍

به روز و متصل بمانید

برای اطمینان از اینکه هیچ بخشی از این سریال را از دست ندهید و برای اطلاعات بیشتر با من در ارتباط باشیدبحث در مورد توسعه نرم افزار (وب، سرور، موبایل یا خراش / اتوماسیون)، داده هاساختارها و الگوریتم‌ها و سایر موضوعات فنی هیجان‌انگیز، من را در این موارد دنبال کنید:

با ما همراه باشید و کدنویسی را شاد کنید 👨‍💻🚀

/** Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head) {
  if (!head) return null;
  if (!head.next) return head;
  let node = null;
  while (head) {
    let currentNode = head.next;
    head.next = node;
    node = head;
    head = currentNode;
  }
  return node;
}

const removeNthFromEnd = function (head, n) {
  // Create a dummy node to handle edge cases (e.g., removing the head)
  const newNode = new ListNode(0);
  newNode.next = head;
  let first = newNode;
  let second = newNode;

  // Move the first pointer n+1 steps ahead
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }

  // Move both pointers until the first pointer reaches the end
  while (first !== null) {
    first = first.next;
    second = second.next;
  }

  // Remove the nth node by updating the next pointer
  second.next = second.next.next;

  // Return the head of the modified list (excluding the dummy node)
  return newNode.next;
};