Skip to content

Latest commit

 

History

History
85 lines (64 loc) · 1.89 KB

反转链表.md

File metadata and controls

85 lines (64 loc) · 1.89 KB
Raw

描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2] 输出：[2,1]

示例 3：

输入：head = [] 输出：[]

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解法

递归

首先想到的是递归，将大问题缩小大小问题，然后在逐步解决。 以[1,2]=>[2,1]为例：

let node1 = { val: 1, next: node2 };
let node2 = { val: 2, next: null };
// 将 [1,2]反转为[2,1]
let node1 = { val: 1, next: null };
let node2 = { val: 2, next: node1 };

这一步中，进行的操作是：

  1. node2(node1.next).next = node1;
  2. node1.next = null;

边界条件是：当 node 本身 或者 node.next 为 null 时，其实就是最后一个，就不必再进行下一步操作了。

function reverseList(head: ListNode | null): ListNode | null {
  if (head == null || head.next == null) {
    // 判断边界条件
    return head;
  }
  // 拿到下一个的递归node
  const newHead = reverseList(head.next);
  // 重复赋值和断开操作
  head.next.next = head;
  head.next = null;
  // 返回操作后的值
  return newHead;
}

迭代

迭代的思路是一样的，先赋值，然后在断开与上一个的链接。

// let node = {val: 1,next: {val: 2,next: null}}
function reverseList(head: ListNode | null): ListNode | null {
  let current = head; // 当前节点
  let prev = null; // 当前节点的前一个节点prev
  while (current) {
    // 保存当前节点的next
    let temp = current.next;
    // 将当前节点的next指向前一个节点
    current.next = prev; 
    // 更新上一个节点
    prev = current; 
    // 更新current
    current = temp;
  }
  return prev;
}

参考