पिछली लिंक्ड सूची को पीछे कैसे पढ़ा जाए?

Question

एक विधि जिसे मैं सोच सकता हूं वह है सूची को पीछे हटाना और फिर इसे पढ़ना। लेकिन इसमें बुरी सूची को बदलना शामिल है।
या मैं सूची की एक प्रति बना सकता हूं और फिर इसे उलट सकता हूं, लेकिन यह अतिरिक्त ओ (एन) मेमोरी का उपयोग करता है। कोई बेहतर तरीका है जिसके अतिरिक्त स्मृति का उपयोग नहीं करता है और सूची को संशोधित नहीं करता है और (एन) समय

रिवर्स लिंक्ड सूची कोड हे में चलता है ग # में कुछ इस तरह

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

ओ (एन) मेमोरी और ओ (एन) प्रदर्शन का उपयोग करने के लिए, एक ढेर बनाएं; जैसे ही आप आगे की दिशा में पुनरावृत्त करते हैं, सबकुछ दबाएं, फिर सबकुछ बंद कर दें, परिणाम प्राप्त करें।

ओ (एन^2) प्रदर्शन (लेकिन ओ (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

खैर, अनुभवहीन समाधान ट्रैक जो नोड के आप पर वर्तमान में कर रहे हैं रखने के लिए, तो शुरू से ही पुनरावृति जब तक आप उस नोड मिल जाए, हमेशा नोड तुम सिर्फ छोड़ दिया बचत होगी। फिर प्रत्येक बार जब आप उस नोड को ढूंढते हैं जो आप वर्तमान में हैं, तो आप जिस नोड को अभी छोड़ चुके हैं, उसका उत्पादन करें, उस नोड को उस समय के रूप में सहेजें जिसे आप वर्तमान में कर रहे हैं, फिर शुरुआत से फिर से पुन: सक्रिय करें।

यह निश्चित रूप से खराब प्रदर्शन-वार होगा।

मुझे यकीन है कि कुछ स्मार्ट लोगों के पास बेहतर समाधान है।

छद्म कोड (कीड़े के साथ भी):

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 3

आप हे में यह पढ़ सकता है (एन^2) - हर बार पिछले नोड को पढ़ने के लिए जाने के लिए और बाहर पिछले एक

Answer 4

प्रिंट

वास्तव में आपको एक दोगुनी-लिंक्ड सूची का उपयोग करना चाहिए।

यदि यह संभव नहीं है, तो मुझे लगता है कि आपका सबसे अच्छा विकल्प सूची की प्रतिलिपि बनाना होगा जो उलट दिया गया है।

अन्य विकल्प, जैसे रिकर्सन पर भरोसा करना (प्रभावी रूप से स्टैक पर सूची की प्रतिलिपि बनाना) यदि सूची बहुत लंबी है तो आपको स्टैक स्पेस से बाहर निकलने का कारण बन सकता है।

Answer 5

यदि आप स्मृति आप, सूची रिवर्स इस पर पुनरावृति और इसे फिर से पलट सकता है की कमी। वैकल्पिक रूप से आप पॉइंटर्स का ढेर नोड्स (या जो भी सी # में पॉइंटर की तरह है) बना सकते हैं।

Answer 6

एकमात्र लिंक वाली सूची के लक्षणों में से एक यह है कि वास्तव में, यह अकेले जुड़ा हुआ है। यह एक तरफा सड़क है, और उस पर काबू पाने का कोई तरीका नहीं है जबतक कि आप इसे किसी और चीज में न बदल दें (जैसे एक उलट एकल-लिंक्ड सूची, एक ढेर, एक दोगुनी-लिंक्ड सूची ...)। चीजों की प्रकृति के लिए एक सच होना चाहिए।

जैसा कि पहले बताया गया है; यदि आपको दोनों तरीकों से एक सूची को पार करने की आवश्यकता है; आपको दोगुनी-लिंक्ड सूची की आवश्यकता है। यह एक दोगुनी लिंक्ड सूची की प्रकृति है, यह दोनों तरीकों से चला जाता है।

Answer 7

यह गंदा है, लेकिन काम करता है:

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 8

अपने अकेले लिंक्ड सूची मान लिया जाये कि IEnumerable लागू करता < टी >, आप LINQ के रिवर्स विस्तार विधि का उपयोग कर सकते हैं:

var backwards = singlyLinkedList.Reverse(); 

आप LINQ के विस्तार विधियों का उपयोग करने के लिए कोड फ़ाइल के शीर्ष पर using System.Linq; निर्देश जोड़ने की आवश्यकता होगी।

Answer 9

ढेर बनाने और सभी तत्वों को ढेर पर धक्का देने की एक भिन्नता रिकर्सन (और प्रणाली के ढेर में निर्मित) का उपयोग करना है, यह शायद उत्पादन कोड के साथ जाने का तरीका नहीं है बल्कि बेहतर (आईएमएचओ) निम्नलिखित कारणों के लिए साक्षात्कार जवाब:

1. इससे पता चलता है आप grok कि प्रत्यावर्तन
2. यह कम कोड है और अधिक सुरुचिपूर्ण
3. एक अनुभवहीन साक्षात्कारकर्ता एहसास नहीं हो सकता एक अंतरिक्ष भूमि के ऊपर है कि वहाँ (यदि यह मामला है प्रतीत होता है आप यह विचार करना चाहेंगे कि आप वहां काम करना चाहते हैं)।

Answer 10

एक तीसरा उपाय है, इस समय O(log(n)) स्मृति और O(n log(n)) समय का उपयोग कर, इस प्रकार मार्क के जवाब में दो समाधान के बीच बीच मैदान पर कब्जा।

इसे प्रभावी ढंग से एक द्विआधारी पेड़ [O(log(n))] की एक रिवर्स में क्रम के वंश, को छोड़कर हर कदम पर आप पेड़ [O(n)] के शीर्ष को खोजने की जरूरत है: दो में

1. स्प्लिट सूची सूची
2. प्रिंट पहली छमाही

में मध्य

recurse पर मूल्य की दूसरी छमाही में

recurse

यहाँ (मैं नहीं जानता कि सी #) पायथन में समाधान है:

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) 

यह प्रत्यावर्तन के बजाय यात्रा का उपयोग कर फिर से पात्र चयन किया जा सकता है, लेकिन स्पष्टता की कीमत पर।

उदाहरण के लिए, एक लाख से प्रवेश सूची के लिए, तीन समाधान के आदेश पर ले:

 
Solution Memory  Performance 
========================================= 
MarC#1  4MB 1 million operations 
    Mine  80B 20 million operations 
MarC#2  4B 1 trillion operations 

Answer 11

क्या बुराई है:

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); 
     } 
    } 

हे (एन) प्रदर्शन, हे (1) मेमोरी और सरल-डू-री-मील के रूप में!

Answer 12

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 13

स्पष्ट ढेर कार्यक्रम में, हम बस प्रत्येक नोड के डेटा के लिए एक ढेर बनाते हैं (प्रकार <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(); 
    } 
}