java-링크 반전 실현-재 귀 와 비 재 귀 실현

20120422 업데이트:
링크 의 일부 노드 에 대해 반전 작업 을 합 니 다.이 노드 들 은 k 개 를 사이 에 두 고 있 습 니 다.
0->1->2->3->4->5->6->7->8->9
k=2
8->1->6->3->4->5->2->7->0->9
1,3,5,7,9 위 치 는 변 하지 않 습 니 다.
해법:
체인 시 계 를 두 부분 으로 나 누 기:
a.0->2->4->6->8
b.1->3->5->7->9
a 부분 을 반전 시 키 고 a 와 b 를 합 칩 니 다.
==update end==

public class LinkListReversing {

	
	public static void main(String[] args) {
		LinkList list=new LinkList();
		int[] a={1,2,3,4,5};
		for(int each:a){
			list.add(each);
		}
		list.display();
		list.reverse();
		list.display();
		list.reverseRecursive(list.getFirstNode());
		list.display();
	}

}


class LinkList{
	
	private Node firstNode;
	private int length;
	
	public LinkList(){
		clear();
	}
	
	public void clear(){
		firstNode=null;
		length=0;
	}
	
	public Node getFirstNode(){
		return firstNode;
	}
	
	public boolean add(int data){
		Node node=new Node(data);
		if(isEmpty()){
			firstNode=node;
		}else{
			Node lastNode=getNodeAt(length);
			lastNode.next=node;
		}
		length++;
		return true;
	}
	
	public boolean isEmpty(){
		//return length==0;
		//use assert to get more details when error occurs
		boolean result;
		if(length==0){
			assert firstNode==null;
			result=true;
		}else{
			assert firstNode!=null;
			result=false;
		}
		return result;
	}
	
	public void reverse(){
		if(firstNode==null)return;
		Node p=firstNode;//use p to traverse every node
		Node previous=null;
		while(p.next!=null){
			Node q=p.next;// save p.next first because the next sentence changes p.next
			p.next=previous;
			previous=p;
			p=q;
		}
		p.next=previous;
		firstNode=p;//should not be ignored
	}
	
	//recursive
	public Node reverseRecursive(Node p){
		if(p==null)return null;
		if(p.next==null){
			firstNode=p;
			return p;
		}
		Node q=p.next;
		//reverse the remaining nodes,except p
		//when recursive returns,you can regard the link as a link that has just two elements: p-->q
		//so the last reversing is simple: q.next=p;p.next=null;
		Node ph=reverseRecursive(q);
		q.next=p;
		p.next=null;
		System.out.print("("+ph.data+")");//ph.data=1,always
		return ph;
	}
	
	public void display(){
		Node node=firstNode;
		while(node!=null){
			System.out.print(node.data+" ");
			node=node.next;
		}
		System.out.println();
	}
	private Node getNodeAt(int position){
		Node re=firstNode;
		if(!isEmpty()&&position>1&&position<=length){
			for(int count=1;count<position;count++){
				re=re.next;
			}
		}
		return re;
	}
	
	//use inner class
	private class Node{
		private int data;
		private Node next;
		
		private Node(int data){
			this.data=data;
			next=null;
		}
	}
}