图片.png

思路：要做到反转链表，其实要做的就是将节点的 next 从指向后一个节点改为指向前一个节点。

方法一：迭代

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     val: number
  5.  *     next: ListNode | null
  6.  *     constructor(val?: number, next?: ListNode | null) {
  7.  *         this.val = (val===undefined ? 0 : val)
  8.  *         this.next = (next===undefined ? null : next)
  9.  *     }
  10.  * }
  11.  */
  13. function reverseList(head: ListNode | null): ListNode | null {
  14.   // 将节点的 next 从指向后一个节点改为指向前一个节点
  16.   let prev: ListNode | null = null 
  17.   let current: ListNode | null = head
  19.   while(current) {
  20.     // 使用一个变量保存当前节点的下一个节点
  21.     const tmp = current.next
  22.     // 将当前节点的 next 指向前一个节点
  23.     current.next = prev
  25.     prev = current 
  26.     current = tmp
  27.   }
  29.   return prev
  30. }

复杂度分析：

  • 时间复杂度：206. 反转链表 - 图2
  • 空间复杂度：206. 反转链表 - 图3

方法二：递归

递归的思想就是将一个过程拆分成一个个更小的过程。

假设链表没有节点或者只有一个节点，那么就应该直接返回传入的 head ：

  1. function reverseList(head: ListNode | null): ListNode | null {
  2.   // 链表没有元素或者只有一个元素的情况
  3.     if (head === null || head.next === null) {
  4.     return head;
  5.   }
  6. }

接下来我们假设链表只有两个节点，那么在前面的处理基础之上，它应该加上第二个节点的 next 指向第一个节点，而第一个节点的 next 指向 null 的操作，并且返回链表最后一个节点：

  1. function reverseList(head: ListNode | null): ListNode | null {
  2.     if (head === null || head.next === null) {
  3.     return head;
  4.   }
  6.   // 当链表只有两个元素的情况
  8.   // 将第二个节点的 next 指向第一个节点
  9.   head.next.next = head;
  10.   // 将第一个节点的 next 指向 null
  11.   head.next = null;
  13.   return head.next.next
  14. }

当链表有两个以上的节点的时候，函数的返回值应返回最后一个节点，而最后一个节点可以通过递归得到。当上面的处理过程再加上通过递归得到最后一个节点，就是本道题目的递归方法题解：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * class ListNode {
  4.  *     val: number
  5.  *     next: ListNode | null
  6.  *     constructor(val?: number, next?: ListNode | null) {
  7.  *         this.val = (val===undefined ? 0 : val)
  8.  *         this.next = (next===undefined ? null : next)
  9.  *     }
  10.  * }
  11.  */
  13. function reverseList(head: ListNode | null): ListNode | null {
  14.   // 当为空链表，或者链表只有一个的时候，直接返回 head
  15.   if (head === null || head.next === null) {
  16.     return head
  17.   }
  19.   const p = reverseList(head.next)
  21.   head.next.next = head;
  22.   head.next = null;
  24.   return p 
  25. }

上面的递归操作，放在操作当前链表节点操作之前，所以设置当前节点后一个节点的 next 以及当前节点的 next 是从链表的最后一个节点开始的。

假设链表为 1 -> 2 -> 3 -> 4 -> 5，会有一下过程：

  1. 当前操作节点为 5 时，函数返回 5 这个节点的引用。
  2. 当前操作节点为 4 时，节点 5 的 next 设置为 4 的引用，而 4 的 next 设置为 null，并返回 5 节点的引用。
  3. 当前操作节点为 3 时，节点 4 的 next 设置为 3 的引用，而 3 的 next 设置为 null，并返回 5 节点的引用。
  4. 当前操作节点为 2 时，节点 2 的 next 设置为 3 的引用，而 2 的 next 设置为 null，并返回 5 节点的引用。
  5. 当前操作节点为 1 时，节点 1 的 next 设置为 2 的引用，而 1 的 next 设置为 null，并返回 5 节点的引用。

复杂度分析：

  • 时间复杂度：206. 反转链表 - 图4
  • 空间复杂度：206. 反转链表 - 图5