---
title: leetcode - Reverse Linked List
date: 2023-02-18
public: true
summary: 反转链表，这次你一定要懂
posterId: 47879
tags:
    - Reverse Linked List
    - 反转链表
    - leetcode
---

> [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/description/)，这个不会建议回炉重造了(说的就是我)。

## recursive

+ Base Case: Rather than a **condition** to keep running, recursive algorithms reach a point to **stop and return**. This point is commonly referred to as the **base case**.
+ Each time you call the function, an argument must change. One argument in particular should be changing *towards* the **base case**.
+ **Establish your base case**. Figure out when the recursion ends! Without a place to stop you’ll wind up overflowing the [call stack](https://en.wikipedia.org/wiki/Call_stack).

```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 {
  // base case, breaking recursive loop
  if (head === null || head.next === null) return head;
  const newHead = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
};
```

## two pointers

```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;
  let cur = head;
  while (cur !== null) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};
```




leetcode - Reverse Linked List

---
title: leetcode - Reverse Linked List
date: 2023-02-18
public: true
summary: 反转链表，这次你一定要懂
posterId: 47879
tags:
    - Reverse Linked List
    - 反转链表
    - leetcode
---

> [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/description/)，这个不会建议回炉重造了(说的就是我)。

## recursive

+ Base Case: Rather than a **condition** to keep running, recursive algorithms reach a point to **stop and return**. This point is commonly referred to as the **base case**.
+ Each time you call the function, an argument must change. One argument in particular should be changing *towards* the **base case**.
+ **Establish your base case**. Figure out when the recursion ends! Without a place to stop you’ll wind up overflowing the [call stack](https://en.wikipedia.org/wiki/Call_stack).

```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 {
  // base case, breaking recursive loop
  if (head === null || head.next === null) return head;
  // head.next.next.next 到 base case, 即最后一个节点(倒数第一个)
  const newHead = reverseList(head.next);
  // 由于是递归，函数栈一直增加，FILO 其实是从后往前处理的。最后处理第一个节点。
  head.next.next = head;
  head.next = null;
  return newHead;
};
```

## two pointers

```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;
  let cur = head;
  // 从头开始处理
  while (cur !== null) {
    // 把 next node 存起来
    const next = cur.next;
    // 按顺序处理 node，把处理过的加到当前处理 node 的 next 指针上
    cur.next = prev;
    // 处理完成的挂到 prev 变量上
    prev = cur;
    // 接下来要处理的，进入下一次循环
    cur = next;
  }
  return prev;
};
```


