菜鸟急求一道JAVA题,高手们花几分钟提点一下小弟吧.不胜感激

Question

模版是这样的
package Chap05.linkList;// linkList.java
// demonstrates linked list
// to run this program: C>java LinkListApp
////////////////////////////////////////////////////////////////
class Link
   {
   public int iData;              // data item
   public double dData;           // data item
   public Link next;              // next link in list
// -------------------------------------------------------------
   public Link(int id, double dd) // constructor
      {
      iData = id;                 // initialize data
      dData = dd;                 // ('next' is automatically
      }                           //  set to null)
// -------------------------------------------------------------
   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 boolean isEmpty()       // true if list is empty
      {
      return (first==null);
      }
// -------------------------------------------------------------
                                  // insert at start of list
   public void insertFirst(int id, double dd)
      {                           // make new link
      Link newLink = new Link(id, dd);
      newLink.next = first;       // newLink --> old first
      first = newLink;            // first --> newLink
      }
// -------------------------------------------------------------
   public Link deleteFirst()      // delete first item
      {                           // (assumes list not empty)
      Link temp = first;          // save reference to link
      first = first.next;         // delete it: first-->old next
      return temp;                // return deleted link
      }
// -------------------------------------------------------------
   public void displayList()
      {
      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("");
      }
// -------------------------------------------------------------
   }  // end class LinkList
////////////////////////////////////////////////////////////////
public class linkListApp
   {
   public static void main(String[] args)
      {
      LinkList theList = new LinkList();  // make new list      theList.insertFirst(22, 2.99);      // insert four items
      theList.insertFirst(44, 4.99);
      theList.insertFirst(77, 7.99);
      theList.insertFirst(66, 6.99);
      theList.insertFirst(88, 8.99);
      theList.insertFirst(99, 9.99);      theList.displayList();              // display list      while( !theList.isEmpty() )         // until it's empty,
         {
         Link aLink = theList.deleteFirst();   // delete link
         System.out.print("Deleted ");         // display it
         aLink.displayLink();
         System.out.println("");
         }
      theList.displayList();              // display list
      }  // end main()
   }  // end class LinkListApp
////////////////////////////////////////////////////////////////
现在有2个要求.
1 对于一个单向链表，写一个方法
   int getLast(int n), 这个方法返回链表倒数第n个节点(就是要键盘输入一个数.然后就返回倒数第N个节点)
2 写一个方法 
   void reverse(), 将这个链表反向(递归?一头雾水啊.高人拉小弟一把吧)

Answer 1

扩展link类，添加index变量。扩展linklist，重写insertFirst方法。之后你那两个问题就容易多了。

Answer 2

定义两个引用，指向首部,移动其中的一个，移动次数等于n时，同时移动两个就ok了

Answer 3

public Link getLast(int n) {

if(n<=0) {
System.out.println("参数应为正整数");
return null;
}

Link result = first;
Link last = result;
int i;
for(i=0; i<n&&last!=null; i++)
last = last.next;
if(i<n) {
System.out.println("链表不够长，没有倒数第"+n+"个元素");
result = null;
}else {
while(last!=null) {
last = last.next;
result = result.next;
}
}
return result;
}

Answer 4

//这是个公共函数，也就是你需要的接口
public void reverse() {
Link temp = first;
while(temp.next!=null)
temp = temp.next;
reverselink(first).next = null;
first = temp;
}
//这是个私有函数，为上面的公共函数服务
private Link reverselink(Link l) {
if(l.next==null)
return l;
reverselink(l.next).next = l;
return l;
}

Answer 5

这个是改进版，代码更简洁，效率更高！！！ //这是个公共函数，也就是你需要的接口
public void reverse() {
Link temp = first;
reverselink(temp).next = null;
}
//这是个私有函数，为上面的公共函数服务
private Link reverselink(Link l) {
if(l.next==null){
first = l;
return l;
}
reverselink(l.next).next = l;
return l;
}