【前端算法】定义一个JS函数，反转单向链表

链表

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

链表 VS 数组

• 都是有序结构
• 链表：查询慢 O(n), 新增和删除快O(1)
• 数组：查询快O(1),新增和删除慢O(n)

创建链表代码示例

interface ILinkNode {
  value: number
  next?: ILinkNode
}

function createLinkNode (arr: number[]): ILinkNode {
  const len = arr.length
  if (len === 0) throw Error('this is a empty array');

  let curNode:ILinkNode = {
    value: arr[len-1]
  }

  if (len === 1) return curNode;

  for(let i = len -2; i >= 0; i--){
    curNode = {
      value: arr[i],
      next: curNode
    }
  }

  return curNode
}

解题思路

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

反转单向链表代码示例

function reverseLinkNode (linkNode:ILinkNode):ILinkNode {
  // 定义3个指针
  let prevNode: ILinkNode | undefined
  let curNode: ILinkNode | undefined
  let nextNode: ILinkNode | undefined = linkNode

  // 以nextNode为主，遍历链表
  while (nextNode) {
    // 删除第一个元素的next，防止循环引用
    if(curNode && !prevNode) {
     delete curNode.next
    }

    // 反转指针
    if (curNode && prevNode) {
      curNode.next = prevNode
    }

    // 整体向后移动
    prevNode = curNode
    curNode = nextNode
    nextNode = (nextNode as ILinkNode)?.next
  }
  // 最后一个补充：当nextNode为空时，curNode没有next时，设置next指向prevNode
  curNode!.next = prevNode

return curNode!
}

功能测试

const arr = [100,200,300]
const link = createLinkNode(arr)
console.log(link)
/*
{
  "value": 100,
  "next": {
    "value": 200,
    "next": {
      "value": 300
    }
  }
}
*/
console.log(reverseLinkNode(link))
/*
{
  "value": 300,
  "next": {
    "value": 200,
    "next": {
      "value": 100
    }
  }
} 
*/

能够跟据数组创建一个完整的单向链表，且反转单向链表功能正常。

单元测试

describe('反转链表', () => {
    it('单个元素', () => {
        const node = { value: 100}
        const node1:ILinkNode = reverseLinkNode(node)
        expect(node1).toEqual({ value: 100})
    })
    
    it('多个元素', () => {
        const arr = [100, 200, 300]
        const node:ILinkNode = createLinkNode(arr)
        const node1:ILinkNode = reverseLinkNode(node)
        expcet(node1).toEqual({
            value: 300,
            next: {
                value: 200,
                next: {
                    value: 100
                }
            }
        })
    })
})