public class SwapNode2 {
    public static ListNode swapNode(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode firstNode = head;
        ListNode secondNode = head.next;

        firstNode.next = swapNode(secondNode.next);
        secondNode.next = firstNode;

        return secondNode;
    }

    public static void main(String[] args){
        ListNode head = new ListNode(1);
        ListNode node1 = new ListNode(2);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        head = swapNode(head);
        ListNode temp = head;
        while (temp != null){
            System.out.println(temp.val);
            temp = temp.next;
        }
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */


 

今天，我们来聊聊递归函数。为啥突然想到递归？其实就从电影名字《恐怖游轮》《盗梦空间》想到了。
递归是啥？
递归函数大家肯定写过，学校上课的时候，估计最开始的例子就是斐波拉契数列了吧。例如：
int Fibonacci(n) {    if (n 
递归函数简而言之就是在一个函数中，由“递归”调用自己。在写递归函数的时候，需要注意的地方就是递归函数的结束条件。用递归函数确实能简化很多算法的实现，比如常见的二叉树遍历等。但往往在写递归函数的时候，最容易出现的问题就是所谓的“栈溢出”。
为什么会有“栈溢出”呢？因为函数调用的过程，都要借助“栈”这种存储结构来保存运行时的一些状态，比如函数调用过程中的变量拷贝，函数调用的地址等等。而“栈”往往存储空间是有限的，当超过其存储空间后，就会抛出著名的异常/错误“StackOverflowError”。
我们以一个简单的加法为例，例如：
int sum(int n) {    if (n <= 1) return n;    return n + sum(n-1);}std::cout << sum(100) <
很简答，编译运行后，比较小的数字，能得到正确的答案，当数字扩大后，就会直接发生“segmentation fault”。
尾递归又是啥？
我得知这个概念，最开始还是因为很多年前一次面试，面试官问我“你知道什么是尾递归吗？”，我以为是“伪”递归，难道是假的递归？？？当初我也是懵逼状态(当初面试官忍住没笑也是厉害了
)。从“尾”字可看出来即若函数在尾巴的地方递归调用自己。上面的例子写成尾递归，就变成了如下：
int tailsum(int n, int sum) {    if (n == 0) return sum;    return tailsum(n-1, sum+n);}
可以试试结果，计算从 1 加到 1000000，仍然是segmentation fault。为什么呢？因为这种写法，本质上还是有多层的函数嵌套调用，中间仍然有压栈、出栈等占用了存储空间(只不过能比前面的方法会省部分空间)。
尾递归优化
当你给编译选项开了优化之后，见证奇迹的时刻到了，居然能算出正确结果。如图所示：
C++ 默认 segmentation fault， 开启编译优化后，能正常计算结果。
原因就是因为编译器帮助做了尾递归优化，可以打开汇编代码看看(这里就不展示 C++的了)。后面我用大家比较熟悉的 JVM based 语言 Scala 来阐述这个优化过程。(好像 Java 的编译器没做这方面的优化，至少我实验我本地 JDK8 是没有的，不清楚最新版本的有木有)(scala 本身提供了一个注解帮助编译器强制校验是否能够进行尾递归优化@tailrec)
object TailRecObject {   def tailSum(n: Int, sum: Int): Int = {        if (n == 0) return sum;        return tailSum(n-1, n+sum);   }   def main(args: Array[String]) {      println(tailSum(100, 0))      println(tailSum(1000000, 0))   }}
结果如下图所示，默认情况下 scalac 做了尾递归优化，能够正确计算出结果，当通过 -g:notailcalls 编译参数去掉尾递归优化后，就发生了 Exception in thread "main" java.lang.StackOverflowError了。
默认启用尾递归优化正常计算结果，禁用尾递归优化则“StackOverflow”。
我们来看看生成的字节码有什么不同。
包含尾递归优化的字节码，直接 goto 循环。
禁用尾递归优化的字节码，方法调用。
从上面可以看出，尾递归优化后，变成循环了(前面的 C++ 类似)。
好了，尾递归咱们就了解到这里。个人看法，我们知道有“尾递归”这个点就好了，有时候我们写递归就是为了方便，代码可读性好，如果确实是出于性能考虑，我们可以自己用迭代的方式去实现，不依赖于具体的编译器实现。当然对于像 scala 这样，有一些语法糖能够帮助校验和验证，也是一个不错的选择。但递归转迭代的能力，我们能具备岂不更好。
作者： 程序猿石头
原文链接：https://mp.weixin.qq.com/s/tccM3lwD2P8v6DTBVFVd4A

不知不觉青铜三人行已经做了两个月的题了，这次轻松点，看看不一样的吧。
机器擅长的事——重复
作为专业的程序猿，经常被行业外的朋友问到，为什么要学习编程？其实，除了掌握技能提高工作效率、甚至成为职业以外。学习编程更重要的是：思维训练。
其实，计算机从一开始就是为了帮助人们解决复杂问题而设计出来的。而在这个过程中，计算机程序的「思考」模型是一个叫“图灵机”的计算模型，图灵机是图灵 (Alan Mathison Turing) 祖师爷模拟人思考而发明出来的。为什么图灵祖师爷要发明图灵机呢？是因为他想要试图以自己和自己周围的天才科学家的思维方式作为人类的具体实例，来抽象总结出一套解决问题的办法。所以说，计算机程序的运作方式其实是一种人类尝试用简单的方式逐步去解决复杂问题的天才的思考方式。
像机器一样思考 - ThoughtWorks洞见​insights.thoughtworks.cn
在如今的时代，计算机早已经充斥在我们生活的方方面面，想要更好地进行人机交互，或多或少地我们都需要一些「像机器一样」的思考方式。即使是作为专业程序员，不断培养自己像机器一样思考的思维模式也是必不可少的。
既然要像机器一样去思考，那么不妨从计算机最擅长的事情——重复，开始说起吧。下面是来自 TED-Ed 中「Think like coder」系列课程的第一节，讲的就是计算机的重复——循环。
From TED-Edhttps://www.zhihu.com/video/1250947428876394496
各种编程语言的循环
来看看在实际编程中，不同编程语言的循环写法有什么不同吧！
for 循环
C
  int jj;
  for (jj=0; jj < 10; jj++) {
    printf("%d, ", jj);
  } // => prints "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "

  printf("n");
Java
// For Loop
        // for loop structure => for(<start_statement>; <conditional>; <step>)
        for (int fooFor = 0; fooFor < 10; fooFor++) {
            System.out.println(fooFor);
            // Iterated 10 times, fooFor 0->9
        }
        System.out.println("fooFor Value: " + fooFor);
Javascript
for (var i = 0; i < 5; i++){
    // will run 5 times
}
Python
for i in range(4):
    print(i)
animals = ["dog", "cat", "mouse"]
for i, value in enumerate(animals):
    print(i, value)
Rust
 // Ranges
    for i in 0u32..10 {
        print!("{} ", i);
    }
    println!("");
    // prints `0 1 2 3 4 5 6 7 8 9 `
Go
 for x := 0; x < 3; x++ { // ++ is a statement.
        fmt.Println("iteration", x)
  }
  for key, value := range map[string]int{"one": 1, "two": 2, "three": 3} {
        // for each pair in the map, print key and value
        fmt.Printf("key=%s, value=%dn", key, value)
    }
while 循环
C
  int ii = 0;
  while (ii < 10) { //ANY value less than ten is true.
    printf("%d, ", ii++); // ii++ increments ii AFTER using its current value.
  } // => prints "0, 1, 2, 3, 4, 5, 6, 7, 8, 9, "

  printf("n");
Java
int fooWhile = 0;
        while(fooWhile < 100) {
            System.out.println(fooWhile);
            // Increment the counter
            // Iterated 100 times, fooWhile 0,1,2...99
            fooWhile++;
        }
        System.out.println("fooWhile Value: " + fooWhile);
JavaScript
// As does `while`.
while (true){
    // An infinite loop!
}
Python
x = 0
while x < 4:
    print(x)
    x += 1  # Shorthand for x = x + 1
Rust
 while 1 == 1 {
        println!("The universe is operating normally.");
        // break statement gets out of the while loop.
        //  It avoids useless iterations.
        break
    }
Go
// Go 语言里面只有 for 循环，但是 for 循环可以不加范围

 for { // Infinite loop.
        break    // Just kidding.
        continue // Unreached.
    }
循环的本质
事实上，不管循环本身的写法和描述有什么改变，它的本质都是一种逻辑判断。也就是说，它们从根本上都是 until 循环的类型：
当某条件满足的时候跳转到循环结束的地方，不然就跳转回循环开始的地方
而基本所有的循环最后大概都会被编译成以下的样子，这叫做汇编语言，它是最接近计算机的思考方式的编程语言了。
        mov eax, val1        ; 把变量 val1 放到 EAX 里面
beginwhile:
        cmp eax, val2        ; 比较 val1 和 val2
        jnl     endwhile     ; 如果 val1 不小于 val2，就跳到 endwhile 的地方
        inc    eax           ; val1++;
        dec    val2          ; val2--;
        jmp    beginwhile    ; 跳回到 beginwhile 的地方
endwhile:
        mov    val1, eax     ;保存 val1 的新值
递归
循环有一对「孪生兄弟」叫做递归。它们的作用都在于解决「重复」的事情。所不同的在于它们对于「重复」的部分的抽象描述不同
如果把要重复执行的指令放在一个「块」里面，称为循环体，并通过外部变量来调整每次循环执行的数据，就叫做循环。
如果把要重复执行的指令抽象成「函数」，并通过传参数的形式来调整每次执行的数据，就称作递归啦！
关于递归的详情可以看看来自 Helen 的视频讲解：
青铜三人行——每周一题@递归讲解_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili​www.bilibili.com
后面
好啦，这次并没有做题，要讲的内容就这么多啦。有时候换换心情和视野也是很重要的，希望这次的内容可以当做故事看看，了解一些更多的事情。下次见啦！

小米1面
二分查找(递归和非递归)
反转链表(递归和非递归)
常用Java集合类
HashMap为什么长度是2的n次幂,数据结构,扩容(包括元素移动的细节),线程不安全的问题
ConcurrentHashMap怎么保证线程安全, 1.7和1 .8有什么变化,为什么要要这么优化
CopyOnWriteL ist怎么保证线程安全，为什么这么做
Java synchronized关键字的作用,原理,锁升级、锁粗化、锁消除
volatile关键字的作用原理
MVCC
事务的ACID ,每- -项是如何保证的
MySQL的索引|结构,为什么是B+树而不是B树
.....
小米2面
先升序后降序的数组排序
求递增数组中相加等于10的元素对
17^400 - 19100计算结果能不能被10整除
一个urI对应一-个random值，要求设计一 一个系统,根据ur|查询random值,具体到表怎么设计,索引怎么加，代码怎么写
讲项目, 画架构图,为什么这么设计,哪一块是你做的,为什么这么做，做了多久
....
小米3面
自我介绍
镜像二叉树(递归和非递归)
删除二叉搜索树的某一个节点
给定数组,求第k大的数字
单例模式的几种写法,解释为什么
tcp握手挥手过程,以及socket的状态变化
线程的状态,以及变化的时机
Java内存模型，堆的组成, gc过程
synchronized修饰同一个类的两个静态***同步吗,为什么
线程池设置了coreSize和maxSize之后,如果线程数量已经达到了coreSize ,这个时候进来-一个任务 ,会
怎么处理
SQL查询优化怎么做
你的优点是什么,缺点是什么
面完回去的路上，HR微信给了我口头offer，嗨心到哭 ~~
现在看来，没过字节的面试还真是自己菜，哭了！！！上次还了分享一些我个人收集的面试资料，真的是有大用处，相信你如果能好好复习，也一定可以拿到想要的offer，这篇文章照例，如果你有需要，可以来找我获取到！
所有的复习资料都是可以免费的分享给有需要的小伙伴们的！如果你需要的话可以转发文章后私信【面试资料】来免费获取到。
01.Spring+Spring boot+SpringMVC 全面复习指南
02.Dubbo+SpringCloud面试指南
还有很多，都保存在WP里了，有需要的小伙伴可以私信我来获取到，因为是截图，所以图片会有些不清楚，文档不会有问题的，请大家伙放心！
关注作者加转发文章后私信【面试资料】来免费获取到上述的文档资料哦！