TS数据结构与算法之反转单向链表

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

反转操作场景

单向链表： A -> B -> C -> D -> E
反转后： E -> D -> C -> B -> A

功能实现

定义节点类型

export interface ListNode {
  value: number;
  next?: ListNode;
}

创建工具方法 createLinkList

根据指定的数组生成一个单链表，如：

const arr = [100, 200, 300, 400];

生成的链表就是：

const linkList = { value: 100, next: { value: 200, next: { value: 300, next: { value: 400 }}}};

/**
 * 根据数组生成单向链表
 */
export const createLinkList = (arr: number[]): ListNode | undefined => {
  let len = arr.length;
  if (!len) return undefined;
  
  let node: ListNode = {
    value: arr[len - 1],
  }

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

  return node;
};

反转链表实现

/**
 * 反转单向链表
 */
export const reverseLinkList = (
  linkList: ListNode | undefined
): ListNode | undefined => {
  if (!linkList) return linkList;
  // 初始化三个节点指针
  let prevNode: ListNode | undefined = undefined;
  let currNode: ListNode | undefined = undefined;
  let nextNode:  ListNode | undefined = linkList;

  // 以 nextNode 为主, 遍历链表
  while (nextNode) {
    // prevNode 不存在时 currentNode 直接断开引用
    if (currNode && !prevNode) {
      delete currNode.next;
    }

    // prevNode 有值直接反转引用
    if (prevNode) {
      currNode!.next = prevNode;
    }

    // 整体向前移动节点指针
    prevNode = currNode;
    currNode = nextNode;
    nextNode = nextNode.next;
  }

  // next 节点无值时少一次循环
  currNode!.next = prevNode;

  return currNode!;
}

单元测试

import { createLinkList, reverseLinkList } from '../src/utils';

describe('反转单向链表单元测试', () => {
  it('应该正确创建单向链表 - createLinkList', () => {
    const arr = [100, 200, 300, 400];
    const linkList = createLinkList(arr);
    const res = {
      value: 100,
      next: {
        value: 200,
        next: {
          value: 300,
          next: {
            value: 400,
          }
        }
      }
    };
    expect(linkList).toEqual(res);
  });

  it('正常反转结果测试', () => {
    const arr = [100, 200, 300, 400];
    const linkList = createLinkList(arr);
    const res = {
      value: 400,
      next: {
        value: 300,
        next: {
          value: 200,
          next: {
            value: 100,
          }
        }
      }
    };
    const reverseList = reverseLinkList(linkList);
    expect(reverseList).toEqual(res);
  });
});

单元测试执行

运行

yarn jest

输出：

 PASS  tests/reverse-link-list.test.ts
  反转单向链表单元测试
    ✓ 应该正确创建单向链表 - createLinkList (3 ms)
    ✓ 正常反转结果测试