---
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

---
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 cur = head;
  while (cur !== null) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};
```




leetcode - Reverse Linked List @ Sun, Feb 19, 2023 6:08 PM			leetcode - Reverse Linked List @ Thu, Feb 23, 2023 7:17 PM
		Expand 56 lines ...
57			57
58		`function reverseList(head: ListNode \| null): ListNode \| null {`	58		`function reverseList(head: ListNode \| null): ListNode \| null {`
59		`let prev = null;`	59		`let prev = null;`
60	-	`let curr` `= head;`	60	+	`let cur` `= head;`
61			61
62	-	`let` `next` `=` `null;`	62	+	`while` `(cur` `!==` `null) {`
63			63
64	-	`while` `(curr !==` `null) {`	64	+	`const next` `=` `cur.next;`
65			65
66	-	`next =` `curr.next;`	66	+	`cur.next =` `prev;`
67			67
68	-	`curr.next` `=` `prev;`	68	+	`prev` `=` `cur;`
69			69
70	-	`prev` `=` `curr;`	70	+	`cur` `=` `next;`
71			71
72	-	`curr = next;`
73		`}`	72		`}`
74		`return prev;`	73		`return prev;`
75		`};`	74		`};`
76		```	75		```