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 occursboolean 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 nodeNode previous=null;while(p.next!=null){Node q=p.next;// save p.next first because the next sentence changes p.nextp.next=previous;previous=p;p=q;}p.next=previous;firstNode=p;//should not be ignored}//recursivepublic 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,alwaysreturn 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 classprivate class Node{private int data;private Node next;private Node(int data){this.data=data;next=null;}}}