当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-实现链表反转-递归和非递归实现

发表于: 2011-12-13   作者:bylijinnan   来源:转载   浏览:
摘要: 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-&
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;
		}
	}
}

java-实现链表反转-递归和非递归实现

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
#include <stdio.h> #include <malloc.h> typedef struct node { int value; struct no
快速排序的核心思想分为两步: 1.选择任何一个数作为基准数,找到这个基准数的位置 2.基准数一侧的
之前有个电话面试,其中一道题就是:用非递归的方式实现文件夹遍历?在电面的时候没有答出来,过后
之前有个电话面试,其中一道题就是:用非递归的方式实现文件夹遍历?在电面的时候没有答出来,过后
2013年03月01日 今天上午在写《编程之美》上面的的链表的逆序的一个思考题,后来在网上无意间发现还
全排列在笔试面试中很热门,因为它难度适中,既可以考察递归实现,又能进一步考察非递归的实现,便
想把算法描述清楚真是件费时费力费脑筋的事情啊,下面的算法描述部分源自以下连接: http://www.cnb
斐波那契数计算的方法一般采用递归的方法,返回类型一般采用int或者long类型。在这种条件下会产生两
http://bbs.chinaunix.net/viewthread.php?tid=331522 http://www.cnblogs.com/SuperXJ/archive/201
1:深度优先 1.1:前序遍历 Visit the root. Traverse the left subtree. Traverse the right subtr
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号