2025-11-25 关于链表(Javascript)

1
// 定义节点类
2
class ListNode {
3
  constructor(value) {
4
    this.value = value; // 节点的值
5
    this.next = null; // 指向下一个节点的指针，初始为 null
6
  }
7
}
8

9
// 定义单向链表类
10
class LinkedList {
11
  constructor() {
12
    this.head = null; // 链表头节点，初始为 null
13
  }
14

15
  // 在链表末尾添加节点
16
  append(value) {
17
    const newNode = new ListNode(value); // 创建一个新的节点
18
    if (this.head === null) {
19
      // 如果链表为空，新的节点作为头节点
20
      this.head = newNode;
21
    } else {
22
      let current = this.head;
23
      while (current.next !== null) {
24
        // 遍历链表找到最后一个节点
25
        current = current.next;
26
      }
27
      current.next = newNode; // 将新的节点添加到最后一个节点的 next
28
    }
29
  }
30

31
  // 在链表头部添加节点
32
  prepend(value) {
33
    const newNode = new ListNode(value); // 创建一个新的节点
34
    newNode.next = this.head; // 新节点的 next 指向当前的头节点
35
    this.head = newNode; // 新节点作为头节点
36
  }
37

38
  // 删除指定值的节点
39
  delete(value) {
40
    if (this.head === null) return; // 如果链表为空，直接返回
41

42
    // 如果头节点就是要删除的节点
43
    if (this.head.value === value) {
44
      this.head = this.head.next;
45
      return;
46
    }
47

48
    let current = this.head;
49
    while (current.next !== null) {
50
      if (current.next.value === value) {
51
        // 找到要删除的节点
52
        current.next = current.next.next; // 将要删除的节点移出链表
53
        return;
54
      }
55
      current = current.next;
56
    }
57
  }
58

59
  // 打印链表
60
  print() {
61
    let current = this.head;
62
    while (current !== null) {
63
      process.stdout.write(`${current.value} -> `); // 输出当前节点的值
64
      current = current.next;
65
    }
66
    console.log("null"); // 表示链表结束
67
  }
68
}
69

70
// 示例：使用单向链表
71
const list = new LinkedList();
72
list.append(1);
73
list.append(2);
74
list.append(3);
75
list.prepend(0);
76
list.print(); // 输出 0 -> 1 -> 2 -> 3 -> null
77
list.delete(2);
78
list.print(); // 输出 0 -> 1 -> 3 -> null

1
// 定义双向节点类
2
class DoublyListNode {
3
  constructor(value) {
4
    this.value = value; // 节点的值
5
    this.next = null; // 指向下一个节点的指针，初始为 null
6
    this.prev = null; // 指向前一个节点的指针，初始为 null
7
  }
8
}
9

10
// 定义双向链表类
11
class DoublyLinkedList {
12
  constructor() {
13
    this.head = null; // 链表头节点，初始为 null
14
    this.tail = null; // 链表尾节点，初始为 null
15
  }
16

17
  // 在链表末尾添加节点
18
  append(value) {
19
    const newNode = new DoublyListNode(value); // 创建一个新的节点
20
    if (this.tail === null) {
21
      // 如果链表为空，新的节点作为头和尾节点
22
      this.head = newNode;
23
      this.tail = newNode;
24
    } else {
25
      this.tail.next = newNode; // 将新的节点添加到尾节点的 next
26
      newNode.prev = this.tail; // 新节点的 prev 指向当前的尾节点
27
      this.tail = newNode; // 新节点作为新的尾节点
28
    }
29
  }
30

31
  // 在链表头部添加节点
32
  prepend(value) {
33
    const newNode = new DoublyListNode(value); // 创建一个新的节点
34
    if (this.head === null) {
35
      // 如果链表为空，新的节点作为头和尾节点
36
      this.head = newNode;
37
      this.tail = newNode;
38
    } else {
39
      this.head.prev = newNode; // 头节点的 prev 指向新的节点
40
      newNode.next = this.head; // 新节点的 next 指向当前的头节点
41
      this.head = newNode; // 新节点作为新的头节点
42
    }
43
  }
44

45
  // 删除指定值的节点
46
  delete(value) {
47
    if (this.head === null) return; // 如果链表为空，直接返回
48

49
    // 如果头节点就是要删除的节点
50
    if (this.head.value === value) {
51
      this.head = this.head.next;
52
      if (this.head !== null) {
53
        this.head.prev = null;
54
      } else {
55
        this.tail = null; // 如果链表为空，更新尾节点
56
      }
57
      return;
58
    }
59

60
    let current = this.head;
61
    while (current !== null) {
62
      if (current.value === value) {
63
        // 找到要删除的节点
64
        if (current.next !== null) {
65
          current.next.prev = current.prev;
66
        } else {
67
          this.tail = current.prev; // 更新尾节点
68
        }
69
        current.prev.next = current.next;
70
        return;
71
      }
72
      current = current.next;
73
    }
74
  }
75

76
  // 打印链表
77
  print() {
78
    let current = this.head;
79
    while (current !== null) {
80
      process.stdout.write(`${current.value} <-> `); // 输出当前节点的值
81
      current = current.next;
82
    }
83
    console.log("null"); // 表示链表结束
84
  }
85
}
86

87
// 示例：使用双向链表
88
const dList = new DoublyLinkedList();
89
dList.append(1);
90
dList.append(2);
91
dList.append(3);
92
dList.prepend(0);
93
dList.print(); // 输出 0 <-> 1 <-> 2 <-> 3 <-> null
94
dList.delete(2);
95
dList.print(); // 输出 0 <-> 1 <-> 3 <-> null

1
/**
2
 * 查找指定值的节点
3
 * @param {LinkedList} list - 单向链表
4
 * @param {any} value - 要查找的值
5
 * @returns {number} - 节点的位置索引，如果未找到返回-1
6
 */
7
function findElement(list, value) {
8
  let current = list.head;
9
  let index = 0;
10

11
  while (current !== null) {
12
    if (current.value === value) {
13
      return index; // 找到值，返回索引
14
    }
15
    current = current.next;
16
    index++;
17
  }
18

19
  return -1; // 未找到，返回-1
20
}
21

22
// 示例：查找元素
23
const searchList = new LinkedList();
24
searchList.append(1);
25
searchList.append(2);
26
searchList.append(3);
27
searchList.append(4);
28

29
console.log(findElement(searchList, 3)); // 输出 2
30
console.log(findElement(searchList, 5)); // 输出 -1

1
/**
2
 * 在指定位置插入节点
3
 * @param {LinkedList} list - 单向链表
4
 * @param {number} position - 插入位置（从0开始）
5
 * @param {any} value - 要插入的值
6
 * @returns {boolean} - 插入成功返回true，否则返回false
7
 */
8
function insertAtPosition(list, position, value) {
9
  if (position < 0) {
10
    return false; // 位置无效
11
  }
12

13
  if (position === 0) {
14
    // 在头部插入
15
    const newNode = new ListNode(value);
16
    newNode.next = list.head;
17
    list.head = newNode;
18
    return true;
19
  }
20

21
  let current = list.head;
22
  let index = 0;
23

24
  // 找到指定位置的前一个节点
25
  while (current !== null && index < position - 1) {
26
    current = current.next;
27
    index++;
28
  }
29

30
  // 如果位置超出链表长度
31
  if (index !== position - 1 && current === null) {
32
    return false;
33
  }
34

35
  // 插入新节点
36
  const newNode = new ListNode(value);
37
  newNode.next = current.next;
38
  current.next = newNode;
39
  return true;
40
}
41

42
// 示例：在指定位置插入元素
43
const insertList = new LinkedList();
44
insertList.append(1);
45
insertList.append(2);
46
insertList.append(4);
47

48
insertList.print(); // 输出 1 -> 2 -> 4 -> null
49
insertAtPosition(insertList, 2, 3); // 在索引2的位置插入3
50
insertList.print(); // 输出 1 -> 2 -> 3 -> 4 -> null
51
insertAtPosition(insertList, 0, 0); // 在开头插入0
52
insertList.print(); // 输出 0 -> 1 -> 2 -> 3 -> 4 -> null

1
/**
2
 * 获取指定位置的元素
3
 * @param {LinkedList} list - 单向链表
4
 * @param {number} position - 位置索引（从0开始）
5
 * @returns {any|undefined} - 位置上的值，如果位置无效返回undefined
6
 */
7
function getElementAtPosition(list, position) {
8
  if (position < 0 || list.head === null) {
9
    return undefined; // 位置无效或链表为空
10
  }
11

12
  let current = list.head;
13
  let index = 0;
14

15
  while (current !== null && index < position) {
16
    current = current.next;
17
    index++;
18
  }
19

20
  if (index === position && current !== null) {
21
    return current.value;
22
  }
23

24
  return undefined; // 位置超出链表长度
25
}
26

27
// 示例：获取指定位置的元素
28
const positionList = new LinkedList();
29
positionList.append(10);
30
positionList.append(20);
31
positionList.append(30);
32

33
console.log(getElementAtPosition(positionList, 0)); // 输出 10
34
console.log(getElementAtPosition(positionList, 2)); // 输出 30
35
console.log(getElementAtPosition(positionList, 5)); // 输出 undefined

1
/**
2
 * 删除指定位置的节点
3
 * @param {LinkedList} list - 单向链表
4
 * @param {number} position - 要删除的位置（从0开始）
5
 * @returns {boolean} - 删除成功返回true，否则返回false
6
 */
7
function deleteAtPosition(list, position) {
8
  if (position < 0 || list.head === null) {
9
    return false; // 位置无效或链表为空
10
  }
11

12
  if (position === 0) {
13
    // 删除头节点
14
    list.head = list.head.next;
15
    return true;
16
  }
17

18
  let current = list.head;
19
  let index = 0;
20

21
  // 找到指定位置的前一个节点
22
  while (current !== null && index < position - 1) {
23
    current = current.next;
24
    index++;
25
  }
26

27
  // 如果位置超出链表长度
28
  if (index !== position - 1 || current.next === null) {
29
    return false;
30
  }
31

32
  // 删除节点
33
  current.next = current.next.next;
34
  return true;
35
}
36

37
// 示例：删除指定位置的元素
38
const deleteList = new LinkedList();
39
deleteList.append(1);
40
deleteList.append(2);
41
deleteList.append(3);
42
deleteList.append(4);
43

44
deleteList.print(); // 输出 1 -> 2 -> 3 -> 4 -> null
45
deleteAtPosition(deleteList, 2); // 删除索引2的位置（值为3）
46
deleteList.print(); // 输出 1 -> 2 -> 4 -> null
47
deleteAtPosition(deleteList, 0); // 删除索引0的位置（值为1）
48
deleteList.print(); // 输出 2 -> 4 -> null

1
/**
2
 * 获取链表长度
3
 * @param {LinkedList} list - 单向链表
4
 * @returns {number} - 链表长度
5
 */
6
function getListLength(list) {
7
  let current = list.head;
8
  let length = 0;
9

10
  while (current !== null) {
11
    length++;
12
    current = current.next;
13
  }
14

15
  return length;
16
}
17

18
// 示例：获取链表长度
19
const lengthList = new LinkedList();
20
lengthList.append(1);
21
lengthList.append(2);
22
lengthList.append(3);
23

24
console.log(getListLength(lengthList)); // 输出 3
25
lengthList.append(4);
26
console.log(getListLength(lengthList)); // 输出 4

1
/**
2
 * 反转单向链表
3
 * @param {LinkedList} list - 单向链表
4
 * @returns {LinkedList} - 反转后的链表
5
 */
6
function reverseLinkedList(list) {
7
  let prev = null;
8
  let current = list.head;
9
  while (current !== null) {
10
    let next = current.next; // 暂存下一个节点
11
    current.next = prev; // 将当前节点的 next 指向前一个节点
12
    prev = current; // 更新前一个节点为当前节点
13
    current = next; // 继续遍历下一个节点
14
  }
15
  list.head = prev; // 更新头节点为最后一个非空节点
16
  return list;
17
}
18

19
// 示例：反转链表
20
const rList = new LinkedList();
21
rList.append(1);
22
rList.append(2);
23
rList.append(3);
24
rList.print(); // 输出 1 -> 2 -> 3 -> null
25
reverseLinkedList(rList);
26
rList.print(); // 输出 3 -> 2 -> 1 -> null

1
/**
2
 * 合并两个有序链表
3
 * @param {LinkedList} l1 - 第一个有序链表
4
 * @param {LinkedList} l2 - 第二个有序链表
5
 * @returns {LinkedList} - 合并后的有序链表
6
 */
7
function mergeTwoLists(l1, l2) {
8
  let dummy = new ListNode(0); // 创建一个哨兵节点
9
  let current = dummy;
10

11
  let p1 = l1.head;
12
  let p2 = l2.head;
13

14
  // 遍历两个链表
15
  while (p1 !== null && p2 !== null) {
16
    if (p1.value < p2.value) {
17
      current.next = p1; // 将较小值的节点添加到结果链表中
18
      p1 = p1.next;
19
    } else {
20
      current.next = p2;
21
      p2 = p2.next;
22
    }
23
    current = current.next;
24
  }
25

26
  // 将剩余的节点连接到结果链表中
27
  if (p1 !== null) {
28
    current.next = p1;
29
  }
30
  if (p2 !== null) {
31
    current.next = p2;
32
  }
33

34
  let mergedList = new LinkedList();
35
  mergedList.head = dummy.next; // 哨兵节点的 next 为合并后的头节点
36
  return mergedList;
37
}
38

39
// 示例：合并两个有序链表
40
const list1 = new LinkedList();
41
list1.append(1);
42
list1.append(3);
43
list1.append(5);
44
const list2 = new LinkedList();
45
list2.append(2);
46
list2.append(4);
47
list2.append(6);
48

49
const mergedList = mergeTwoLists(list1, list2);
50
mergedList.print(); // 输出 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null