用React构建fiber树的思想解决“反转链表”问题

最近在阅读React源码，还是比较有收获的，这不，今天刷题的时候，直接就把React渲染组件的思想给落地了，并且好像也知道了如何去写React原理专栏。

看题吧：

就是这样，给你一个单链表，要求你把单链表反向输出。

接下来我们来看一下如何使用React渲染组件的思想来把这道题AC。

function ListNode(val, next){
    this.val = (val === undefined) ? 0 : val;
    this.next = (next === undefined) ? null : next;
}

let vdom1 = new ListNode(1);
let vdom2 = new ListNode(2);
let vdom3 = new ListNode(3);
let vdom4 = new ListNode(4);
let vdom5 = new ListNode(5);

vdom1.next = vdom2;
vdom2.next = vdom3;
vdom3.next = vdom4;
vdom4.next = vdom5;

上面就是创建了一个ListNode的构造函数，使用这个构造函数可以创建出一条单链表，如下：

1 -> 2 -> 3 -> 4 -> 5

如何实现翻转链表呢？我们似乎也只有遍历这一条路可走吧，如下：

let reverseList = function (head){
    // 存储当前正在工作的节点
    let workInProgressFiber = head;
    
    // 这个用来存储翻转后的链表
    let result = new ListFiber(0, null);
    let result1 = result;
    
    while(workInProgressFiber){
        // 对链表上的每个node都进行相应的工作
        performUnitOfWork(workInProgressFiber, result)
    }
    
    // 将结果返回
    return result1.next;
}

上面的代码工作流程如下：

1、存储当前遍历到的节点（workInProgressFiber）。

2、对每个节点都进行工作处理（performUnitOfWork）。

3、当workInProgressFiber为空时，意味着链表已经遍历完成，那此时应该将翻转后的链表返回。

那接下来的关键，就是看看performUnitOfWork函数应该如何实现呗，代码如下：

function performUnitOfWork(curWorkInProgressFiber, result){
    // 获取下一个节点
    let nextWorkInProgressFiber = curWorkInProgressFiber.next;
    
    if (!nextWorkInProgressFiber){
        // 说明已经是链表的尾部了，开始归阶段
        completeWork(curWorkInProgressFiber, result);
        // 归阶段结束后，结束整个workLoopSync
        curWorkInProgressFiber = null;
        return
    }
    
    // 让下一个节点的return属性指向当前节点
    nextWorkInProgressFiber.return = curWorkInProgressFiber;
    
    // 将当前节点指向下一个节点，开启下一个performUnitOfWork
    curWorkInProgressFiber = nextWorkInProgressFiber;
}

上述思想如下：

1、将 下一个节点的return属性 指向 当前节点。

2、当遍历到尾部时，咱们最原始的 单链表 就变为了 双向链表。

3、双向链表不是最终答案，根据当前节点的return属性可以找到上级（开启归阶段），我们可以这个关系构建出真正的反转链表。

所以，我们来着重观察下completeWork是如何工作的：

function completeWork(curFiber, result){
    while(curFiber){
        curFiber.next = null;
        result.next = curFiber;
        curFiber = curFiber.return;
        result = result.next;
    }
}

completeWork工作流程如下：

1、自底向上的通过return属性拿到上级节点。

2、将当前节点加入到result表里，因为是自底向上，所以当completeWork工作完成后，我们就可以得到一个翻转的链表。

最后，我们就解决了一个“翻转链表”的问题，leetcode上可以看到执行用时：

用时上也还说的过去，当然React里还有一种更高效的思路可以解决这个问题，那就是收集update。我们都知道组件内部的同类型更新，是通过环形链表来维护的，你可以把一个节点当作一次更新，说到这里，剩下的就交给各位大佬了，欢迎各位把答案发到讨论区里。

以上就是这次的分享内容，其实这个问题还是很简单的，用React思想来解决这种问题并不是最优解，但它可以锻炼你对React源码的理解，所以我觉着还是很有营养的，那么我们下期再见啦，拜拜～～

原文链接：https://juejin.cn/post/7325647896048369705 作者：小九九的爸爸