كيفية قراءة قائمة مرتبطة منفردة للخلف؟

Question

طريقة واحدة يمكنني التفكير فيها هي عكس القائمة ثم اقرأها. ولكن هذا ينطوي على تغيير القائمة التي هي سيئة.
أو يمكنني تقديم نسخة من القائمة ثم عكسها، ولكن هذا يستخدم ذاكرة O (N) إضافية. هل هناك أي طريقة أفضل لا تستخدم الذاكرة الإضافية ولا تعدل القائمة وتشغيلها في وقت O (N)

رمز القائمة المرتبطة عكس شيء مثل هذا في C #

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

        while (current!=null)
        {
            nextNode = current.Next;
            current.Next = prev;
            prev=current;
            current = nextNode; 

        }
        head = prev;

}   

الحل العريض هو

void ReadBackWard (Node n)
{
    if (n==null)
        return;
    else
        ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

Answer 1

لاستخدام o (n) الذاكرة وأداء O (n)، قم بإنشاء مكدس؛ ادفع كل شيء عند التكرار في اتجاه الأمام، ثم ينبثق كل شيء، مما يؤدي إلى النتائج.

لاستخدام الأداء O (n ^ 2) (ولكن o (1) الذاكرة الإضافية)، اقرأه إلى الأمام في كل مرة، حتى العقدة قبل آخر واحد حصلت عليه.

مثال:

IEnumerable<T> Reverse (Node head) {
    Stack<Node> nodes = new Stack<Node>();
    while(head != null) {
        nodes.Push(head);
        head = head.Next;
    }
    while(nodes.Count > 0) {
        yield return nodes.Pop().Value;
    }
}

Answer 2

واحدة من السمات المميزة لقائمة مرتبطة منفردة هي أنه، في الواقع، مرتبط منفردة. إنه شارع ذو اتجاه واحد، ولا توجد وسيلة للتغلب على أنه ما لم تقم بتحويله إلى شيء آخر (مثل قائمة عكسية مرتبطة منفردة، كومة، قائمة مرتبطة مضاعفة ...). يجب أن يكون المرء صحيحا في طبيعة الأشياء.

كما أشار في وقت سابق؛ إذا كنت بحاجة إلى اجتياز قائمة كلا الاتجاهين؛ تحتاج إلى الحصول على قائمة مرتبطة مضاعفة. هذه هي طبيعة قائمة مرتبطة مضاعفة، فهي تذهب إلى كلا الاتجاهين.

Answer 3

في الحقيقة يجب أن تستخدم قائمة مرتبطة مضاعفة.

إذا لم يكن ذلك ممكنا، فما أعتقد أن خيارك الأفضل سيكون لبناء نسخة من القائمة التي تم عكسها.

يمكن أن تتسبب الخيارات الأخرى، مثل الاعتماد على العودية (نسخ القائمة بفعالية القائمة على المكدس) لنفذ مساحة المكدس إذا كانت القائمة طويلة جدا.

Answer 4

إذا قمت باختصار الذاكرة، فيمكنك عكس القائمة، وتكررها وعكسها مرة أخرى. بدلا من ذلك، يمكنك إنشاء كومة من المؤشرات إلى العقد (أو أي شيء مثل مؤشر في C #).

Answer 5

void reverse_print(node *head) 
{
    node *newHead = NULL, *cur = head;

    if(!head) return;

    // Reverse the link list O(n) time O(1) space
    while(cur){
        head = head->next;
        cur->next = newHead;
        newHead = cur;
        cur = head;
    }

    // Print the list O(n) time O(1) space
    cur = newHead;
    while(cur) {
        printf(" %d", cur->val);
        cur = cur->next;
    }

    // Reverse the link list again O(n) time O(1) space
    cur = newHead;
    while(cur){
        newHead = newHead->next;
        cur->next = head;
        head = cur;
        cur = newHead;
    }
    // Total complexity O(n) time O(1) space
}

Answer 6

هناك حل ثالث، هذه المرة باستخدام O(log(n)) الذاكرة و O(n log(n)) الوقت، وبالتالي احتلال الأرض الوسطى بين الحلول في إجابة مارك.

من النزول بشكل فعال في ترتيب الشجرة الثنائية [O(log(n))]، إلا في كل خطوة تحتاج إلى العثور على الجزء العلوي من الشجرة [O(n)]:

1. تقسيم القائمة في اثنين
2. تواصل إلى النصف الثاني من القائمة
3. طباعة القيمة عند نقطة المنتصف
4. تواصل إلى النصف الأول

هنا هو الحل في بيثون (لا أعرف C #):

def findMidpoint(head, tail):
  pos, mid = head, head
  while pos is not tail and pos.next is not tail:
    pos, mid = pos.next.next, mid.next
  return mid

def printReversed(head, tail=None):
  if head is not tail:
    mid = findMidpoint(head, tail)
    printReversed(mid.next, tail)
    print mid.value,
    printReversed(head, mid)

قد يكون هذا إعادة صياغته باستخدام التكرار بدلا من العودية، ولكن بتكلفة الوضوح.

على سبيل المثال، للحصول على قائمة بدخول مليون، تأخذ الحلول الثلاثة حسب:

أداء ذاكرة الحل ========================================= Marc # 1 4MB 1 مليون العمليات المنجم 80B 20 مليون عملية مارك # 2 4B 1 تريليون العمليات

Answer 7

على افتراض أن قائمة قوائمك المرتبطة المنفردة IEnumerableu003CT> ، يمكنك استخدام طريقة التمديد العكسي LINQ:

var backwards = singlyLinkedList.Reverse();

ستحتاج إلى إضافة using System.Linq; التوجيه في الجزء العلوي من ملف التعليمات البرمجية لاستخدام طرق ملحق LinQ.

Answer 8

هناك اختلاف لإنشاء مكدس ودفع جميع العناصر الموجودة على المكدس هو استخدام العودية (والنظام المدمج في المكدس)، ربما يكون هذا هو الطريقة التي يجب أن تذهب مع رمز الإنتاج ولكنها بمثابة إجابة أفضل (IMHO) إجابة الأسباب التالية:

1. هذا يدل على أنك grok secursion
2. إنه أقل رمز ويظهر أكثر أناقة
3. قد لا يدرك البقاحات السذاجة أن هناك مساحة واحدة (إذا كانت هذه هي الحالة التي قد ترغب في التفكير فيها عما إذا كنت تريد العمل هناك).

Answer 9

حسنا، سيكون الحل الساذج هو تتبع العقدة التي تعمل حاليا، ثم تكررت من البداية حتى تجد تلك العقدة، وتوفر دائما العقدة التي تركتها للتو. ثم في كل مرة تقوم فيها بالعثور على العقدة التي تقوم بها حاليا، يمكنك إنتاج العقدة التي تركتها فقط، وحفظ العقدة كواحدة تعمل حاليا، ثم إعادة التكرار من البداية.

سيكون هذا بالطبع أداء سيئا بشكل فظيع.

أنا متأكد من أن بعض الأشخاص الأكثر ذكاء لديهم حل أفضل.

الكود الزائفي (مع الأخطاء حتى):

current node = nothing
while current node is not first node
    node = start
    while node is not current node
        previous node = node
        node = next node
    produce previous node
    set current node to previous node

Answer 10

هذا فوضوي ولكن يعمل:

class SinglyLinkedList {
SinglyLinkedList next;
int pos;
SinglyLinkedList(int pos) {
    this.pos = pos;
}
SinglyLinkedList previous(SinglyLinkedList startNode) {
    if (startNode == this) return null;
    if (startNode.next == this) return startNode;
    else return previous(startNode.next);
}

static int count = 0;
static SinglyLinkedList list;
static SinglyLinkedList head;
static SinglyLinkedList tail;
public static void main (String [] args) {
    init();

    System.out.println("Head: " + head.pos);
    System.out.println("Tail: " + tail.pos);

    list = head;
    System.out.print("List forwards: ");
    while (list != null) {
        System.out.print(list.pos + ",");
        list = list.next;
    }

    list = tail;
    System.out.print("\nList backwards: ");
    while (list.previous(head) != null) {
        System.out.print(list.pos + ",");
        list = list.previous(head);
    }
}
static void init() {
    list = new SinglyLinkedList(0);
    head = list;
    while (count < 100) {
        list.next = new SinglyLinkedList(++count);
        list = list.next;
    }
    tail = list;
}

}

Answer 11

إذا كان في برنامج المكدس الصريح، فنحن نخلق كومة لبيانات كل عقدة (بدلا من إنشاء كومة من النوع <Node>, ، ونحن نخلق كومة من النوع <T>) أليس كذلك أفضل؟ لأننا لا نحتاج إلى تخزين أي معلومات أخرى من العقدة إذن.

IEnumerable<T> Reverse (Node<T> head) {
    Stack<T> nodes = new Stack<T>();
    while(head != null) {
        nodes.Push(head.data);
        head = head.Next;
    }
    while(nodes.Count > 0) {
        yield return nodes.Pop();
    }
}

Answer 12

يمكنك قراءتها في O (n ^ 2) - في كل مرة تذهب إلى آخر عقدة اقرأ وطباعتها السابقة

Answer 13

ما المشكلة في:

    public void printBackwards(LinkedList sl){    
        ListIterator<Element> litr = sl.listIterator(sl.size());
        Element temp;
        while(litr.previousIndex() >= 0){
            temp = litr.previous();
            System.out.println(temp);
        }
    }

o (n) الأداء، O (1) الذاكرة وبسيطة مثل DO-RE-MI!