LeetCode-206.反转链表

题目详解

相关链接

• 代码随想录

思路

• 遍历一遍链表，利用双指针将每个节点的指向反转

看完代码随想录之后的想法

• 学会了递归写法

实现过程中遇到的困难

• while循环的终止条件，最终返回值需要注意 容易出错

代码

• 双指针迭代

TypeScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
  let prev = null,
    cur = head
  while (cur) [cur.next, prev, cur] = [prev, cur, cur.next]
  return prev
}

时间复杂度：O(n)
空间复杂度：O(1)

• 递归

TypeScript

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
  return reverse(head, null)
}

function reverse(cur: ListNode | null, prev: ListNode | null): ListNode | null {
  if (!cur) return prev
  const tmp = cur.next
  cur.next = prev
  return reverse(tmp, cur)
}

时间复杂度：O(n)
空间复杂度：O(1)

收获

• 链表的操作顺序一定要理清楚 不能乱，否则很容易断链