找个方式降低你的心智模型复杂度.md

date	tags
2019-04-25	思考

链表的几个典型的题有种特别的调性，思路很简单，但是过程中总是各种引用换方向，还有指针移动，往往代码却不那么容易写，但是会有种“慢慢写总会写出来”的感觉，这类问题就会造成学习过程中的心智模型太复杂的情况，或者转化成纯粹的记忆，这样就大错特错了。有一个更清晰的心智模型，对于这种类型的问题帮助很大。

对于此类问题：

• 先不管代码是否能运行，把引用变化的步骤拆解，分步骤写出来，每一行单独运行都是正确的。
• 再审查这些步骤上下是否有副作用。
• 如果有副作用，通过提前存储变量消除副作用。

举个例子：https://leetcode.com/problems/swap-nodes-in-pairs/

一次循环里我们要换三个指针，并且移动prev和head两个指针，对应下面的a,b,c。假设每一步都是独立事件，那么对于每一步，我们可以很容易的写出下面代码。

var swapPairs = function(head) {
    if (!head) {
        return head
    }
    var dhead = new ListNode(0)
    dhead.next = head
    var prev = dhead
    
    while(head && head.next) {
        // a
        head.next = head.next.next
        // b
        head.next.next = head
        // c
        prev.next = head.next
        
        prev = head
        head = head.next
    }
    return dhead.next
};

但是上面代码不能直接运行，原因很简单，因为在执行的过程中，有些引用被改变且在后面又被引用，我们要做点手脚让这些步骤可以真的相互独立。

var swapPairs = function(head) {
    if (!head) {
        return head
    }
    var dhead = new ListNode(0)
    dhead.next = head
    var prev = dhead
    
    while(head && head.next) {
        var tmp = head.next // 缓存并在下面替换
        // a
        head.next = head.next.next
        // b
        tmp.next = head
        // c
        prev.next = tmp
        
        prev = head
        head = head.next
    }
    return dhead.next
};

说好的相对孤立，所以按照常理，那这几步调换一下顺序也是可以的，例如：

// c
prev.next = head.next
// b
head.next.next = head
// a
head.next = head.next.next

那么问题c,b,a的过程中实际上head.next.next的引用被修改了且需要被后面使用，所以按照上面的思路将其缓存。

var swapPairs = function(head) {
    if (!head) {
        return head
    }
    var dhead = new ListNode(0)
    dhead.next = head
    var prev = dhead
    
    while(head && head.next) {
        var tmp = head.next.next
        // c
        prev.next = head.next
        // b
        head.next.next = head
        // a
        head.next = tmp
        
        prev = head
        head = head.next
    }
    return dhead.next
};

在举个例子：https://leetcode.com/problems/reverse-linked-list/

var reverseList = function(head) {
    var prev = null
    while(head) {
        head.next = prev
        prev = head
        head = head.next // head.next 在前面被改变，而影响了
    }
    return prev
};

var reverseList = function(head) {
    var prev = null
    while(head) {
        var tmp = head.next // 缓存然后替换
        head.next = prev
        prev = head
        head = tmp
    }
    return prev
};

对于其他问题呢？虽然思路是不一样的，但是可以肯定的是简化问题才能更好的领悟。有了更简洁清晰的心智模型，我们能确保事情正确，且正确的明明白白。