第89题 反转一个单项链表

• 链表是一个物理结构，类似于数组
• 数组需要一段连续的内存空间，而链表是零散的
• 链表节点的数据结构 {value,next?, prev?}

链表vs数组

• 链表和数组都是有序结构
• 链表：查询慢（把链表全部遍历一遍查询）时间复杂度：O(n)，新增和删除快（修改指针指向）时间复杂度：O(1)
• 数组：查询快（根据下标）时间复杂度：O(1)，新增和删除慢（移动元素）时间复杂度：O(n)

链表的应用

react fiber使用了链表

    // 双向链表基本结构演示
    const n1 = {value:1,next:n2} // 头节点没有prev
    const n2 = {value:2,next:n3,prev:n1}
    const n3 = {value:3,next:n4,prev:n2}
    const n4 = {value:4,prev:n3} // 尾节点没有next
    
    // 串联起来大致如下
    const link = {
      value: 1,
      next: {
        value: 2,
        prev: {
          value: 1,
          ...
        },
        next: {
          value: 3,
          prev: {
            value: 2,
            ...
          },
          next: {
            value: 4
          }
        }
      }
    }

反转一个单项链表解题思路

• 反转，即节点的next指向前一个节点
• 但很容易造成nextNode的丢失
• 需要三个指针 prevNode、curNode、nextNode

    // listNode的数据类型
    interface ILinkListNode {
      value: number
      next?: ILinkListNode
    }
    
    /**
     * 反转单向链表，并返回反转之后的 head node
     * @param listNode list head node
     */
    function reverseLinkList(listNode) {
        // 定义三个指针
        let prevNode = undefined // 上一个节点
        let curNode = undefined // 当前节点
        let nextNode = listNode // 默认赋值listNode
    
        // 以 nextNode 为主，遍历链表
        while(nextNode) {
          // ABCD 第一个元素A反转后没有next，需要删掉 next ，防止循环引用
          if (curNode && !prevNode) {
            delete curNode.next
          }
    
          // 反转指针
          if (curNode && prevNode) {
            curNode.next = prevNode
          }
    
          // 整体向后移动三个指针
          prevNode = curNode // 把当前节点赋给上一个节点
          curNode = nextNode // 把下一个节点赋给当前节点
          nextNode = nextNode.next // 把下一个节点的next节点赋给下一个节点
        }
    
        // 对指针移动到最后一个元素nextNode的处理：当 nextNode 空时，此时 curNode 尚未设置 next
        // https://s.poetries.work/uploads/2023/01/e3a852412a0563dd.png
        curNode.next = prevNode
    
        return curNode
    }

    // 功能测试
    
    /**
     * 根据数组创建单向链表
     * @param arr number arr
     */
    function createLinkList(arr) {
        const length = arr.length
        if (length === 0) throw new Error('arr is empty')
    
        // [1,2,3]
        // 最后一个{value:3}
        let curNode = {
            value: arr[length - 1]
        }
        if (length === 1) return curNode
    
        // 从倒数第二个开始 [1,2,3]
        // {value:2,next:{value:3}}
        // {value:1,next:{value:2,next:{value:3}}}
        for (let i = length - 2; i >= 0; i--) {
            curNode = {
                value: arr[i],
                next: curNode
            }
        }
    
        return curNode
    }
    
    var arr = [100, 200, 300, 400, 500]
    var list = createLinkList(arr)
    /**反转前
     * {
     *    value: 100,
     *    next: {
     *      value: 200,
     *      next: {
     *        value:300,
     *        next: {
     *          value: 400,
     *          next: {
     *            value: 500
     *          }
     *        }
     *      }
     *    }
     * }
     */
    console.info('list:', list) 
    
    var list1 = reverseLinkList(list)
    
    /**反转后
     * {
     *    value: 500,
     *    next: {
     *      value: 400,
     *      next: {
     *        value:300,
     *        next: {
     *          value: 200,
     *          next: {
     *            value: 100
     *          }
     *        }
     *      }
     *    }
     * }
     */
    console.info('list1:', list1)