【数据结构与算法】(7)：反转单向链表

链表是一种 动态且零散 的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。本文介绍一下如何将数组变成链表，并且实现 反转单向链表 的算法。

一、链表 VS 数组

• 链表特点

• 链表 VS 数组

二、数组转单向链表

• TS 代码演示

interface ILinkListNode {
  value: number
  next?: ILinkListNode
}

type ItemNode = ILinkListNode | undefined

function createLinkList(arr: number[]): ILinkListNode {
  const len = arr.length;
  if (len === 0) throw new Error('arr is empty');

  let currNode: ILinkListNode = {
    value: arr[len - 1]
  }

  if (len===1) return currNode

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

  return currNode
}

三、反转单向链表

1. 反转单向链表思路图示

2. TS 代码演示

function reverseLinkList(listNode: ILinkListNode): ILinkListNode {
  let prevNode: ItemNode = undefined
  let currNode: ItemNode = undefined
  let nextNode: ItemNode = listNode

  while (nextNode) {
    // 第一个元素删掉 next ，防止循环引用
    if (currNode && !prevNode) {
      delete currNode.next
    }

    // 反转指针
    if (currNode && prevNode) {
      // @ts-ignore
      currNode.next = prevNode
    }

    // 指针整体向后移
    prevNode = currNode
    currNode = nextNode
    nextNode = nextNode?.next

  }

  // 最后一个补充：当 nextNode 为空时，此时 currNode 尚未设置 next 指向
  currNode!.next = prevNode

  return currNode!
}

四、测试

const arr = [100, 200, 300, 400, 500]
const res = createLinkList(arr)
console.log(res)
let str1 = JSON.stringify(res)
let link1 = JSON.parse(str1)
let list1 = reverseLinkList(link1)
console.log(list1)

数组转链表输出：

{
    "value": 100,
    "next": {
        "value": 200,
        "next": {
            "value": 300,
            "next": {
                "value": 400,
                "next": {
                    "value": 500
                }
            }
        }
    }
}

反转链表输出：

{
    "value": 500,
    "next": {
        "value": 400,
        "next": {
            "value": 300,
            "next": {
                "value": 200,
                "next": {
                    "value": 100
                }
            }
        }
    }
}

《数据结构与算法》系列

1. 什么是算法复杂度
2. 堆(heap)、栈(stack)、队列(queue)
3. 把一个数组旋转k步
4. 判断字符串是否括号匹配
5. 数组、栈、链表、队列结构与对比
6. 用两个栈实现一个队列
7. 反转单向链表
8. 用链表实现队列
9. 二分查找
10. 查找两数之和

欢迎访问：天问博客