Ex1_3_28 递归返回节点最大值

Ex1_3_28 递归返回节点最大值

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_28_maxNode<Item> {
    private class Node{
        Item item;
        Node next;
    }
    private Node head;
    private int N = 0;
    public boolean isEmpty(){
        return head == null;
    }
    public int size(){
        return N;
    }
    public void headInsert(Item item){
            Node node = head;
            head = new Node();
            head.item = item;
            head.next = node;
            N++;
    }
    public void headRemove(){
        if (isEmpty()) throw new RuntimeException("Queue underflow");
        else{
            head = head.next;
            N--;
        }
    }
    public int max(Node max, Node node){
        if(max == null) return 0;//空链表
        else if(node == null) return (int)max.item;//最大值
        else{
            if((int)max.item > (int)node.item){
                return max(max, node.next);
            }else return max(node, node.next);
        }
    }
    public static void main(String[] args){
        Ex1_3_28_maxNode m = new Ex1_3_28_maxNode();
        while (!StdIn.isEmpty()){
            int a = StdIn.readInt();
            m.headInsert(a);
        }
        StdOut.println(m.max(m.head,m.head.next));
    }
}

要点:

1. 链表实现,采用头插头删
2. 递归初始接收head,head.next为参数;当开始head == null说明是空链表,返回0,当node == null说明链表已经遍历完毕,返回max