链表

什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针指向null。

指针的类型

单向链表：只有数据域和指向下一个节点的指针域。
双向链表：每一个节点具有两个指针域，一个指向下一个节点，一个指向上一个节点。
环形链表：链表首位相连。

链表的存储方式

链表在内存中不是连续分布的，通过指针域中的指针指向链接在内存中的各个节点。所以链表的内存分布是散乱的分布在内存的某地址上，分配机制取决于操作系统的内存管理。

链表节点的定义

如下是一个链表节点的类：

typescript

/**
 * val:节点值
 * next:指向下一节点的引用
 */
class ListNode {
  constructor(public val?: number, public next?: ListNode | null) {}
}

链遍常用操作：

初始化链表：

typescript

const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);

插入节点

typescript

/* 在链表的节点 n0 之后插入节点 P */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

删除节点

typescript

/* 删除链表的节点 n0 之后的首个节点 */
function remove(n0: ListNode): void {
    if (!n0.next) {
        return;
    }
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

访问节点

typescript

/* 访问链表中索引为 index 的节点 */
function access(head: ListNode | null, index: number): ListNode | null {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

练习题

INFO

题意：删除链表中等于给定值 val 的所有节点。

示例 1：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2：输入：head = [], val = 1 输出：[]

示例 3：输入：head = [7,7,7,7], val = 7 输出：[]

代码示例:

typescript

/**
 * val:节点值
 * next:指向下一节点的引用
 */
class ListNode {
  constructor(public val?: number, public next?: ListNode | null) {}
}

function removeElements(head: ListNode | null, val: number): ListNode | null {
  //使用虚拟头节点的方式
  const dumyHead = new ListNode()
  dumyHead.next = head
  //定义一个临时指针
  let cur = dumyHead
  while (cur.next != null) {
    if (cur.next.val == val) {
      cur.next = cur.next.next
    } else cur = cur.next
  }
  return dumyHead.next
}

INFO

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

代码示例:

typescript

/**
 * val:节点值
 * next:指向下一节点的引用
 */
class ListNode {
  constructor(
    public val?: number,
    public next?: ListNode | null,
  ) {}
}

class MyLinkedList {
  // 记录链表长度
  constructor(
    private size: number = 0,
    private head: ListNode | null = null,
    private tail: ListNode | null = null,
  ) {}

  // 获取链表中第 index 个节点的值
  get(index: number): number {
    // 索引无效的情况
    if (index < 0 || index >= this.size) {
      return -1
    }
    let curNode = this.getNode(index)
    // 这里在前置条件下，理论上不会出现 null的情况
    return curNode.val!
  }

  // 在链表的第一个元素之前添加一个值为 val的节点。插入后，新节点将成为链表的第一个节点。
  addAtHead(val: number): void {
    let node: ListNode = new ListNode(val, this.head)
    this.head = node
    if (!this.tail) {
      this.tail = node
    }
    this.size++
  }

  // 将值为 val 的节点追加到链表的最后一个元素。
  addAtTail(val: number): void {
    let node: ListNode = new ListNode(val, null)
    if (this.tail) {
      this.tail.next = node
    } else {
      // 还没有尾节点，说明一个节点都还没有
      this.head = node
    }
    this.tail = node
    this.size++
  }

  // 在链表中的第 index个节点之前添加值为 val的节点。
  // 如果 index等于链表的长度，则该节点将附加到链表的末尾。如果 index大于链表长度，则不会插入节点。如果 index小于0，则在头部插入节点。
  addAtIndex(index: number, val: number): void {
    if (index === this.size) {
      this.addAtTail(val)
      return
    }
    if (index > this.size) {
      return
    }
    // <= 0 的情况都是在头部插入
    if (index <= 0) {
      this.addAtHead(val)
      return
    }
    // 正常情况
    // 获取插入位置的前一个 node
    let curNode = this.getNode(index - 1)
    let node: ListNode = new ListNode(val, curNode.next)
    curNode.next = node
    this.size++
  }

  // 如果索引 index有效，则删除链表中的第 index个节点。
  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) {
      return
    }
    // 处理头节点
    if (index === 0) {
      this.head = this.head!.next!
      // 如果链表中只有一个元素，删除头节点后，需要处理尾节点
      if (index === this.size - 1) {
        this.tail = null
      }
      this.size--
      return
    }
    // 索引有效
    let curNode: ListNode = this.getNode(index - 1)
    curNode.next = curNode.next!.next
    // 处理尾节点
    if (index === this.size - 1) {
      this.tail = curNode
    }
    this.size--
  }

  // 获取指定 Node节点
  private getNode(index: number): ListNode {
    // 这里不存在没办法获取到节点的情况，都已经在前置方法做过判断
    // 创建虚拟头节点
    let curNode: ListNode = new ListNode(0, this.head)
    for (let i = 0; i <= index; i++) {
      // 理论上不会出现 null
      curNode = curNode.next!
    }
    return curNode
  }
}

INFO

题意：反转一个单链表。
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

双指针写法:

typescript

function reverseList(head: ListNode | null): ListNode | null {
  //初始化,pre是链表反转之后链表尾部节点指向null。并添加指针cur指向头部节点
  let pre = null,cur = head
  //遍历链表,结束条件为：原链表的当前节点为null的时候结束遍历
  while (cur) {
    //临时指针存储当前节点的，防止节点丢失
    let temp = cur.next
    //破坏节点的方向，将当前节点的后继节点变成它的前驱节点，实现节点之间方向的反转
    cur.next = pre
    //移动pre的指针让它向前移动一个节点
    pre = cur
    //cur指针也向前推动一个节点
    cur = temp as ListNode | null
  }
  //当cur指针指向null的时候，循环结束，此时pre为反转链表的头部节点
  return pre
}

递归写法：

typescript

function reverse(cur: ListNode | null, pre: ListNode | null): ListNode | null {
  //递归终止的条件，就是当前节点的为null，此时 pre 代表反转之后的链表的头部节点
  if (cur == null) return pre
  //临时存储当前节点的后继节点的引用
  let temp = cur.next as ListNode | null
  //破坏节点的方向，将当前节点的后继节点指向 pre 节点的引用，就是指向当前节点的前一个节点
  cur.next = pre
  //递归调用,实现cur,prev指针向前移动一位
  return reverse(temp, cur)
}

function reverseList(head: ListNode | null): ListNode | null {
  //初始化，第二个参数传递null是反转链表之后的新链表的尾部节点的nest域指向null
  return reverse(head, null)
}

INFO

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

代码示例:

typescript

/**
 * val:节点值
 * next:指向下一节点的引用
 */
class ListNode {
  constructor(public val?: number, public next?: ListNode | null) {}
}

function swapPairs(head: ListNode | null): ListNode | null {
  //生成虚拟头节点
  const dumyHead = new ListNode()
  //虚拟头节点的next域指向原链表头节点
  dumyHead.next = head
  //要操作原链表的第一个和第二个节点，需要将cur指针放在虚拟头节点的位置（大体的思路是：如果要操作索引为1，2的元素，则需要将cur指针指向索引为0的节点）
  let cur = dumyHead
  while (cur?.next != null && cur?.next!.next != null) {
    //缓存要操作的第一个节点
    const temp = cur.next
    //缓存第二个节点的 next 域的的引用，如果不缓存的话，在改变第二个节点的 next 域指向第一个节点的时候（为了实现交换），原来指向第三个节点的引用会丢失
    const temp1 = cur.next.next?.next
    //将指向第一个节点的引用指向第二个节点（实现将第二个节点元素交换到第一个节点元素的位置）
    cur.next = cur.next.next
    //将第二个节点的引用指向第一个节点，实现将第一个元素换到第二个节点的位置
    cur.next!.next = temp
    //将新链表的第二个节点的引用指向原链表的第二个节点的next域的引用
    temp.next = temp1
    //推进cur指针指向下个要被操作的两个元素之前的节点
    cur = cur.next!.next
  }
  //返回新链表头部节点
  return dumyHead.next
}

INFO

删除列表中倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

代码示例：

typescript

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dumyHead = new ListNode();
  dumyHead.next = head;
  //防止当n大于链表长度，指针提前为null。
  n++;
  //初始化快慢指针
  let fast = dumyHead,slow = dumyHead;
  //先让快指针移动 n + 1步
  while (n-- && fast != null) {
    fast = fast.next!;
  }
  //然后快慢指针同时移动，此时如果快指针迭代到null的时候，慢指针刚好位于被删除元素的前一个元素
  while (fast != null) {
    fast = fast.next!;
    slow = slow.next!;
  }
  //改变慢指针的指向的节点的next域实现删除节点
  slow.next = slow.next?.next;
  return dumyHead.next;
}

INFO

环形链表

题意：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

代码示例：

typescript

function detectCycle(head: ListNode | null): ListNode | null {
  let slowNode: ListNode | null = head,
    fastNode: ListNode | null = head;
  while (fastNode !== null && fastNode.next !== null) {
    slowNode = slowNode!.next!;
    fastNode = fastNode.next!.next!;
    if (slowNode === fastNode) {
      slowNode = head;
      while (slowNode !== fastNode) {
        slowNode = slowNode!.next!;
        fastNode = fastNode!.next!;
      }
      return slowNode;
    }
  }
  return null;
}

链表 ​

指针的类型 ​

链表的存储方式 ​

链表节点的定义 ​

练习题 ​

链表

指针的类型

链表的存储方式

链表节点的定义

练习题