linked list per reverse() "umdrehen"

[javalala]

nabend leute.

vertiefe mich grade etwas in das thema datenstrukturen und bin auf folgende aufgabe gestoßen zu der ich erst mal nicht weiter weiss. :bahnhof:

1.Aufgabe (Liste, stack, queue, array)
Schreiben sie Java-Code für eine Methode reverse(), die als Parameter eine durch ihren First-Pointer gegebene einfach verkettete Liste erhält. Die Methode soll als Rückgabewert einen First-Pointer auf eine Liste liefern, die der ursprünglichen in umgekehrter Reihenfolge entspricht. Für eine Lösung, bei der die einzelnen Listenelemente nicht zwischengespeichert werden, gibt es Extrapunkte.

weiss nicht so recht wie ich diese aufgabe angehen soll.bin dankbar für jegliche anregung etc.

gruß javalala :###

 

[Der Müde Joe]

eine LLElement enthält ja einen Pointer (referenz) auf das nächste Element der Kette und das letzte auf null:

1 - 2 - 3 - 4 - null;

also Element 1 zeigt auf Element 2 .... und 4 auf null

nachher

1 zeigt auf null ... 4 auf 3
2 zeigt auf 1 ... 3 auf 2 ...

das System sollte also klar sein

EDIT
4 - 3 - 2 - 1 - null
so ists nachher

 

[javalala]

hallo joe.

danke schon mal für deine antwort so spät am abend
ja also das system/konzept ist mir soweit klar, aber wie könnte ich das programmiertechnisch umsetzen (ohne zwischenspeicherung wie "gefordert")? vllt mit einem zusätzlichen array?

gruß

 

[Ariol]

//Beispielliste anlegen
		List<Integer> ll = new LinkedList<Integer>();
		ll.add(1);
		ll.add(2);
		ll.add(3);
		ll.add(4);
		ll.add(5);
		ll.add(6);
		ll.add(7);
		ll.add(8);

		//Testausgabe
		System.out.println(ll.toString());
		
		//Drehen
		for(int i = ll.size()-1; i>=0; i--)
		{
			ll.add(ll.get(i));
			ll.remove(i);
		}
		
		//Testausgabe
		System.out.println(ll.toString());

 

[Der Müde Joe]

so auf die schnell

nimm 1. Element: setze next auf null
temp= 1;
tempNext: next
nimm 2. Element (tempNext): setze next auf temp
temp=2;
tempNext: next
nimm 3. Element: setze next auf temp
tempNext: next
.....
nimm letztes Element: .... auf temp (2.letztes)

....return letztes Element...welches auf 2. l zeigt...welches auch 3.l zeigt...----..welches auf null zeigt.

halt eben so auf schnell

EDIT:
@Ariol...hab ich mit auch gedacht...aber
>die als Parameter eine durch ihren First-Pointer gegebene einfach verkettete Liste erhält
also reverse(Element first);

 

[javalala]

@ariol
ja das wäre eine schöne lösung aber bekomme ja leider nur den firstpointer übergeben.

@joe
diesen weg versteh ich noch nicht so richtig

nimm 1. Element: setze next auf null
temp= 1;
tempNext: next

da versteh ich schon nicht so recht was was ist.aber war ja auch nur auf die schnelle und es ist ja schon spät...
ich schau es mir morgen früh nochmal genau an, vllt kannst du ja morgen noch eine etwas detaillierte version posten wenn du willst, wäre jedenfalls cool

gruß

 

[Der Müde Joe]

@joe
diesen weg versteh ich noch nicht so richtig

nimm 1. Element: setze next auf null
temp= 1;
tempNext: next

du erhälst das 1. element (mit Referenz auf das 2.)

also
tempLast = null (Schluss);

nimm dieses Element (firstPointer).
speichere die Referenz auf das nächste Element ( tempNextElementToChange = Element.next)
speichere als neues next das tempLast (Element.next = tempLast)
speichere das aktuelle Element (tempLast = Element)

nun das ganze mit dem nächsten element ( tempNextElementToChange ) usw...
wenn das tempNextElementToChange == null ist das ende erreicht (nun das erste element mit einer referenz auf das zweitlezte)

 

[javalala]

morgen.

also ich paste grade mal den code von der liste mit der ich arbeite.

package aufgabe1;

////////////////////////////////////////////////////////////////
class Link
   {
   public int iData;              // data item (key)
   public double dData;           // data item
   public Link next;              // next link in list
// -------------------------------------------------------------
   public Link(int id, double dd) // constructor
      {
      iData = id;
      dData = dd;
      }
// -------------------------------------------------------------
   public void displayLink()      // display ourself
      {
      System.out.print("{" + iData + ", " + dData + "} ");
      }
   }  // end class Link
////////////////////////////////////////////////////////////////
class LinkList
   {
   private Link first;            // ref to first link on list

// -------------------------------------------------------------
   public LinkList()              // constructor
      {
      first = null;               // no links on list yet
      }
// -------------------------------------------------------------
   public void insertFirst(int id, double dd)
      {                           // make new link
      Link newLink = new Link(id, dd);
      newLink.next = first;       // it points to old first link
      first = newLink;            // now first points to this
      }
// -------------------------------------------------------------
   public Link find(int key)      // find link with given key
      {                           // (assumes non-empty list)
      Link current = first;              // start at 'first'
      while(current.iData != key)        // while no match,
         {
         if(current.next == null)        // if end of list,
            return null;                 // didn't find it
         else                            // not end of list,
            current = current.next;      // go to next link
         }
      return current;                    // found it
      }
// -------------------------------------------------------------
   public Link delete(int key)    // delete link with given key
      {                           // (assumes non-empty list)
      Link current = first;              // search for link
      Link previous = first;
      while(current.iData != key)
         {
         if(current.next == null)
            return null;                 // didn't find it
         else
            {
            previous = current;          // go to next link
            current = current.next;
            }
         }                               // found it
      if(current == first)               // if first link,
         first = first.next;             //    change first
      else                               // otherwise,
         previous.next = current.next;   //    bypass it
      return current;
      }
// -------------------------------------------------------------
   public void displayList()      // display the list
      {
      //System.out.print("List (first-->last): ");
      Link current = first;       // start at beginning of list
      while(current != null)      // until end of list,
         {
         current.displayLink();   // print data
         current = current.next;  // move to next link
         }
      System.out.println("");
      }

habe jetzt mal versucht das umzusetzen, irgendwie steh ich aufm schlauch, weiss nich wieso ich mir da so schwer tue...

package aufgabe1;

public class Umdrehen {

	private static aufgabe1.LinkList mylist = new aufgabe1.LinkList();
	
	public static void fill() {
		for (int i = 4; i >= 0; i--) {
			mylist.insertFirst(i, 0.0);
		}
	}
	
	public static Link reverse(Link firstLink) {
		Link current = firstLink;
		Link tempNextElementToChange = current;
		Link tempLast = null;
		
		while (tempNextElementToChange != null) {
			tempNextElementToChange = current.next;
			current.next = tempLast;
			tempLast = current;
		}
		return current;
	}
	
	public static void main(String[] args) {
		fill();
		mylist.displayList();
		reverse(mylist.find(0));
		System.out.println("----");
		mylist.displayList();
	}
}

 

[Der Müde Joe]

bei deiner reverse bleibt "current" immer das erste elemnt

das aktuelle Element ist nat. das was im durchgang davor
als nextToChange deklarieret wurde.

 

[tuxedo]

Mir fällt da spontan "BubbleSort" ein... Nur um mal ein tolles Stichwort in den Raum zu werfen.

 

[Der Müde Joe]

Mir fällt da spontan "BubbleSort" ein... Nur um mal ein tolles Stichwort in den Raum zu werfen.

mir fälllt spontan "Bierpause" ein.....

>Schreiben sie Java-Code für eine Methode reverse(), die als Parameter eine durch ihren First-Pointer gegebene einfach verkettete Liste erhält.

also kanns nur in der Braun'schen Röhre blubbern.

 

[tuxedo]

Ich sagte ja auch "spontan" und nicht "durchdacht" ;-)

- Alex