常见算法（二）

背景

面试过程中，特别是一些大公司，对于程序员的要求越来越高，你必须会一些和本职工作没什么关系的技能，这样才能使你stand out，面试其实是需要精心准备的，也许你在面试完后，这些东西你都用不到，但是为了那个offer你还是要去准备，这些可以概括为“面试造航母，工作拧螺丝”，另一方面，这些知识其实对我们自身来说是有用的（有用和无用其实不好定义，而且看似无用的东西往往它的生命周期会更长），它能帮我们开阔眼界，系统搭建我们的知识架构，让我们掌握的东西能串起来，而且我们在未来碰到问题的时候可以多一种选择。算法就是这样一个东西。

单向链表转置

这个问题其实是很常见的一个算法问题，但是如果没弄清楚就会被它给搞晕了，从晕到不晕的过程就是你理解该算法的过程。

算法还是需要理解它，才能真正的去掌握它

下图是一个单向链表转置的初始状态和终止状态。

转置后：

链表

首先要知道链表的数据结构是怎么样的，链表首先有自己的值（value），其次它有一个指针指向了下个结点，我们用代码来表示是这样的：

class Node{
    public int value;
    
    public Node next;
    
    public Node(int data){
        this.value = data
    }
}

从上面代码可以很清楚的看到链表的特点，他是区别于数组的一种数据结构。

链表和数组

在数组中，是通过==索引==来访问元素的，很多算法都是利用索引来操作的，所以数组这种数据结构可以快速的查询到数据。
链表的优势则是删除/插入数据，因为数组是固定长度的，所以增删都会改变数组的所有元素（下标变化了），而链表是可以动态改变大小的，他只会影响左右相邻的两个结点。另外链表在内存中的存储不是连续的。

算法分析过程

先上代码

public Node reverseList(Node head){
    //临时变量
    Node pre = null
    Node next = null
    
    while(head != null){
        next = head.next // 1
        head.next = pre // 2
        
        pre = head  //3
        head = next. //4
    }
    
    return pre
}