---
title: leetcode - Reverse Linked List
date: 2023-02-18
public: true
summary: 反转链表，这次你一定要懂
tags:
    - Reverse Linked List
    - 反转链表
    - leetcode
---

> [Reverse Linked List](https://leetcode.com/problems/reverse-linked-list/description/)，这个不会建议回炉重造了(说的就是我)。

## recursive

```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 curr = head;
  let next = null;
  while (curr !== null) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};
```




leetcode - Reverse Linked List

---
title: leetcode - Reverse Linked List
date: 2023-02-18
public: true
summary: 反转链表，这次你一定要懂
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 curr = head;
  let next = null;
  while (curr !== null) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
};
```




leetcode - Reverse Linked List @ Sun, Feb 19, 2023 9:27 AM		leetcode - Reverse Linked List @ Sun, Feb 19, 2023 6:08 PM
	Expand 12 lines ...
13		13
14	`## recursive`	14		`## recursive`
15		15
		16	+	`+ 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.`
		17	+	`+ Each time you call the function, an argument must change. One argument in particular should be changing towards the base case.`
		18	+	`+ 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).`
		19	+
16	```typescript	20		```typescript
17	`/**`	21		`/**`
18	`* Definition for singly-linked list.`	22		`* Definition for singly-linked list.`
	Expand 48 lines ...