基础算法之递归函数——链表的创建（java）

深藏阁楼爱情的钟 2022-05-16 00:19 74阅读 0赞

# 通过递归方法实现创建链表 #

要求：给入一个数组，把数组里的每一个元素生成一个节点，然后让节点首尾相接，链表以null结尾，链表必须第一个结点点作为链表头。  
递归要点  
1. 先一般后特殊  
2. 将大规模问题缩小

## 链表元素创建 ##

public class Node {
        private final int value;
        private Node next;
    
        public Node(int value){
       //构造方法，生成是给定初值
            this.value=value;
            this.next=null;
        }
    
        public int getValue() {
            return value;
        }
    
        public Node getNext() {
            return next;
        }
    
        public void setNext(Node next) {
            this.next = next;
        }
        //打印函数
        public static void printLinkedList(Node head){
            while (head!=null){
                System.out.println(head.getValue());
                System.out.println(head.getNext());
                head=head.getNext();
            }
            System.out.println();
        }
    
        @Override
        public String toString() {
       //toString方法，可以让我们更加清晰了解链表结构
            return "Node{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

## 创建链表 ##

public class LinkedListCreator { 
        /** * Creates linked list * @param data * @return */
       public Node createLinkedList(List<Integer> data){
           if (data.isEmpty()){
       //特殊情况
               return null;
           }
    
            Node firstNode =new Node(data.get(0));
            firstNode.setNext(createLinkedList(data.subList(1,data.size())));//关键点：清楚subList用法
            return firstNode;
       }
        public void add(Integer num)
        {
            Node firstNode =new Node(num);
    
        }
    
        public static void main(String[] args) {
            LinkedListCreator creator=new LinkedListCreator();
    
            Node.printLinkedList(creator.createLinkedList(Arrays.asList(1,2,3,4,5,6,7)));
        }
    }

## 运行后的结果 ##

1
    Node{
       value=2, next=Node{
       value=3, next=Node{
       value=4, next=Node{
       value=5, next=Node{
       value=6, next=Node{
       value=7, next=null}}}}}}
    2
    Node{
       value=3, next=Node{
       value=4, next=Node{
       value=5, next=Node{
       value=6, next=Node{
       value=7, next=null}}}}}
    3
    Node{
       value=4, next=Node{
       value=5, next=Node{
       value=6, next=Node{
       value=7, next=null}}}}
    4
    Node{
       value=5, next=Node{
       value=6, next=Node{
       value=7, next=null}}}
    5
    Node{
       value=6, next=Node{
       value=7, next=null}}
    6
    Node{
       value=7, next=null}
    7
    null