java-兑现链表反转-递归和非递归实现
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==
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; } } }