使用js反转单向链表

发表于 更新于 分类于
使用js反转单向链表

题目如下

  • 请使用js反转单向链表

补充：

  • 链表是一种物理结构（非逻辑结构），类似于数组
  • 数组需要一段连续的内存空间，而链表是零散的
  • 链表节点的数据结构 {value,next?,prev?}
  • 链表查询慢O(n)，新增和删除快O(1)
  • 数组查询快O(1)，新增和删除慢O(n)
  • React Fiber使用了链表

思路如下

  • 首先根据数组创建一个链表
  • 反转，即节点next指向前一个节点，但这很容易造成nextnode丢失
  • 此时需要三个指针：prevNode、curNode、nextNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
 * @description 反转单向链表
 * @author sola-grj
 * 链表 查询慢O(n)，新增和删除快O(1)
 * 数组 查询快O(1)，新增和删除慢O(n)
 */

// 链表基础结构接口
export interface ILinkListNode {
    value: number;
    next?: ILinkListNode;
}


// 根据数组创建单向链表,从数组最后一个元素向前进行构造
export function createLinkList(arr:number[]): ILinkListNode {
  const length = arr.length
  if(length === 0) throw new Error("array is empty")
  
  let curNode: ILinkListNode = {
    value:arr[length - 1]
  }
  if(length === 1) return curNode
  
  for(let i = length - 2;i >= 0;length--) {
    curNode = {
      value:arr[i],
      next:curNode
    }
  }
  
  return curNode
}

// 反转单向链表，并返回反转之后的head node
export function reverseLinkList(listNode:ILinkListNode): ILinkListNode {
  // 定义三个指针
  let prevNode: ILinkListNode | undefined = undefined;
  let curNode: ILinkListNode | undefined = undefined;
  let nextNode: ILinkListNode | undefined = listNode;
  
  while(nextNode){
    // 第一个元素，删掉next，防止循环引用
    if(curNode && !prevNode){
      delete curNode.next
    }
    
    // 反转指针
    if(curNode && prevNode){
      curNode.next = prevNode
    }
    
    // 整体向后移动指针
    prevNode = curNode;
    curNode = nextNode;
    nextNode = nextNode?.next
  }
  
  // 最后一个的补充：当 nextNode 空时，此时 curNode 尚未设置 next
    curNode!.next = prevNode;

    return curNode!;
}

单元测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @description 反转单向链表 test
 * @author 双越老师
 */

import { ILinkListNode, reverseLinkList, createLinkList } from './reverse-link-list'

describe('反转单向链表', () => {
    it('单个元素', () => {
        const node: ILinkListNode = { value: 100 }
        const node1 = reverseLinkList(node)
        expect(node1).toEqual({ value: 100 })
    })
    it('多个元素', () => {
        const node = createLinkList([100, 200, 300])
        const node1 = reverseLinkList(node)
        expect(node1).toEqual({
            value: 300,
            next: {
                value: 200,
                next: {
                    value: 100
                }
            }
        })
    })

})