java逆转单链表_JAVA_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > JAVA > java逆转单链表

java逆转单链表

 2014/4/19 3:44:37  qq346359669  程序员俱乐部  我要评论(0)
  • 摘要:节点类://节点类classNode{publicNode(intvalue){this.value=value;}publicNode(){}intvalue;Nodenext;}初始化链表//初始化一个有序的单链表publicNodeinitList(){Nodehead=newNode();Noden1=newNode();Noden2=newNode();Noden3=newNode();Noden4=newNode();Noden5=newNode();n1.value=1;n2
  • 标签:单链表 Java

节点类:
class="java" name="code">
//节点类
class Node{
	public Node(int value){
		this.value = value;
	}
	public Node(){
	}
	int value;
	Node next;
}

初始化链表
//初始化一个有序的单链表
	public Node initList(){
		Node head = new Node();
		Node n1 = new Node();
		Node n2 = new Node();
		Node n3 = new Node();
		Node n4 = new Node();
		Node n5 = new Node();
		n1.value = 1;
		n2.value = 2;
		n3.value = 3;
		n4.value = 4;
		n5.value = 5;
		n1.next = n2;
		n2.next = n3;
		n3.next = n4;
		n4.next = n5;
		head.next = n1;
		return head;
	}

递归的逆转
//单链表逆转,非递归
	public Node reverseList(Node node){
		if (null == node) {   
            return node;   
        }
		//上一个节点
        Node upper = null;   
        //当前节点
        Node cur = node.next;
        //下一个节点
        Node next = null;   
        while (null != cur) {   
            next = cur.next;   
            cur.next = upper;
            upper = cur;   
            cur = next;   
        }
        //反转结束后,upper引用指向原链表的最后一个节点,即反转后的第一个节点
        node = upper;   
           
        return node;   
	}

递归的逆转
public Node reverse(Node node){
		if(node==null || node.next == null)return node;
		Node next = node.next;
//将node的next清空,否则在递归return到最上层时要逆转的原链表的最后一个节点的next会指向原来的头节点,而原来的头节点的next又指向原来的第一个节点,即逆转后的最后一个节点,会造成无限的重复链表
		node.next = null;
		Node returnNode = reverse2(next);
		next.next = node;
		return returnNode;
	}

打印链表:
//打印单链表
	public void printList(Node head){
		String str = "";
		for(Node n = head;n!=null;){
			str = str + " " + n.value;
			n = n.next;
		}
		System.out.println(str);
	}

调用:
Test t = new Test();
		Node head = t.initList();
		System.out.println("逆转前:");
		t.printList(head.next);
		System.out.println("逆转后:");
		t.printList(t.reverseList(head));

上一篇: java单链表冒泡排序 下一篇: 浅谈GC调优
发表评论
用户名: 匿名