通过ListNode了解普通循环，迭代和递归_listnode怎么递归

前言 ：这几天在刷面试题的时候做到一个关于ListNode的时候蒙圈了，然后查了一下资料，突然又发现自己傻傻分不清普通循环，迭代和递归的区别了。

ListNode

public class ListNode {
    int val;  //值
    ListNode next;  // 下一个节点对象
    ListNode(int x){ //赋值链表的值
        val = x ;
    }
}
1
2
3
4
5
6
7

普通循环，迭代和递归介绍

• 迭代：函数内某段代码实现循环。循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。在循环的次数较大的时候，迭代的效率明显高于递归。
• 递归： “To Iterate is Human, to Recurse, Divine.”中文译为：“人理解迭代，神理解递归。”，重复调用函数自身实现循环。

通过listNode了解普通循环，迭代和递归区别

import com.sun.scenario.effect.Merge;
import listNode.ListNode;

/**
 * @author hdd
 * @Date 2021/2/4
 */
public class ListNode1 {
    public static void main(String[] args){
        ListNode x = new ListNode(3);
        ListNode y = new ListNode(6);
        ListNode z = new ListNode(8);
        x.next = y;
        y.next = z;
        System.out.println("x:"+x.next.val);
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(7);
        ListNode c = new ListNode(9);
        a.next = b;
        b.next = c;
        System.out.println("a:"+a.next.val);

        ListNode l1 = merge(a,x);
        while(l1 != null){
            System.out.println("l1:"+l1.val);
            l1 = l1.next;
        }

    }
    /* 迭代： 根据ListNode特性，我们只需要返回一个头部(head)ListNode对象就可以了。*/
    public static ListNode merge(ListNode list1, ListNode list2) {
        // 如果list1 为空，说明包含list1的链表没有listNode对象，下同理。
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                /**
                 *  如果list2的值小于list1,就将list2对象加入到p的链表中去，同时list2的链表和p的链表都向下移动一个节点，
                 *  套用指针理解就是指针所指向链表的对象在变化。
                 *  后面同理。
                 *  */
                p.next = list2;
                list2 = list2.next;
                p = p.next;
            }else{
                p.next = list1;
                list1 = list1.next;
                p = p.next;
            }
        }
        /* 如果其中一个链表循环空了，那么将另一个链表的节点部位加入到p的链表 */
        p.next = list1 == null ? list2 : list1;
        return head.next;
    }

    /* 递归： 那个小就返回那个对象，后续使用递归一直排序 */
    public static ListNode merge2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        if (list1.val < list2.val) {
            list1.next = merge2(list1.next, list2);
            return list1;
        }else{
            list2.next = merge2(list1, list2.next);
            return list2;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

总结：merge2()非常简洁！！
递归基本需要以下三个条件：

1. 递归结束的条件 ；
2. 缩小问题规模同时不重叠 ；
3. 问题结果如何结合成最终结果。