链表重排（链表快速排序）

## 链表重排### 简介链表重排是指调整链表中节点的顺序以满足特定条件的操作。常见链表重排序类型包括：

链表反转:

将链表的顺序完全颠倒。

奇偶链表:

将链表重排序，使得所有奇数索引的节点位于偶数索引节点之前，并保持原始的相对顺序。

指定基准分割:

根据给定值将链表分割成两部分，一部分节点的值小于基准值，另一部分节点的值大于等于基准值。### 链表重排方法链表重排可以使用迭代或递归方法实现。下面详细介绍几种常见的链表重排序类型及其代码实现。#### 1. 链表反转##### 1.1 迭代法迭代法使用三个指针：`prev`， `curr` 和 `next`。`curr` 指向当前节点，`prev` 指向 `curr` 的前一个节点，`next` 指向 `curr` 的下一个节点。算法的基本思想是：1. 初始化 `prev` 为 `null`，`curr` 为链表头节点。 2. 迭代遍历链表，每次迭代执行以下步骤：

将 `next` 指向 `curr` 的下一个节点。

将 `curr` 的 `next` 指针指向 `prev`，反转当前节点的指向。

将 `prev` 指向 `curr`，`curr` 指向 `next`，移动到下一个节点。 3. 返回 `prev`，它现在指向反转后链表的头节点。

代码示例 (Python):

```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev ```##### 1.2 递归法递归法利用递归函数的调用栈来反转链表。基本思想是：1. 递归到链表的最后一个节点，将其作为反转后链表的头节点。 2. 在递归返回的过程中，反转当前节点与其后继节点之间的指向。

代码示例 (Python):

```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head: ListNode) -> ListNode:if not head or not head.next:return headnew_head = reverseList(head.next)head.next.next = headhead.next = Nonereturn new_head ```#### 2. 奇偶链表奇偶链表重排序可以使用两个指针 `odd` 和 `even` 分别指向奇数和偶数节点。基本思想是：1. 初始化 `odd` 指向头节点，`even` 指向头节点的下一个节点。 2. 迭代遍历链表，每次迭代执行以下步骤：

将 `odd.next` 指向 `even.next`。

将 `odd` 指向 `odd.next`。

将 `even.next` 指向 `odd.next`。

将 `even` 指向 `even.next`。 3. 最后将 `odd.next` 指向 `even_head`，连接奇数链表和偶数链表。 4. 返回原始链表的头节点。

代码示例 (Python):

```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef oddEvenList(head: ListNode) -> ListNode:if not head or not head.next:return headodd = headeven = head.nexteven_head = evenwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = even_headreturn head ```#### 3. 指定基准分割指定基准分割可以使用两个指针 `smaller` 和 `larger` 分别指向小于和大于等于基准值的节点。基本思想是：1. 创建两个虚拟节点 `smaller_head` 和 `larger_head` 分别作为小于和大于等于基准值的链表的头部。 2. 初始化 `smaller` 指向 `smaller_head`，`larger` 指向 `larger_head`。 3. 迭代遍历链表，根据当前节点的值将其连接到 `smaller` 或 `larger` 指针的后面。 4. 最后将 `smaller.next` 指向 `larger_head.next`，连接两个链表。 5. 返回 `smaller_head.next`，即分割后小于基准值的链表的头节点。

代码示例 (Python):

```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef partition(head: ListNode, x: int) -> ListNode:smaller_head = ListNode(0)larger_head = ListNode(0)smaller = smaller_headlarger = larger_headwhile head:if head.val < x:smaller.next = headsmaller = smaller.nextelse:larger.next = headlarger = larger.nexthead = head.nextsmaller.next = larger_head.nextreturn smaller_head.next ```### 总结链表重排是链表操作中的常见问题，可以通过迭代和递归方法实现。理解不同类型的链表重排方法，并根据具体需求选择合适的算法，对于提高代码效率和解决实际问题至关重要。

链表重排

简介链表重排是指调整链表中节点的顺序以满足特定条件的操作。常见链表重排序类型包括：* **链表反转:** 将链表的顺序完全颠倒。 * **奇偶链表:** 将链表重排序，使得所有奇数索引的节点位于偶数索引节点之前，并保持原始的相对顺序。 * **指定基准分割:** 根据给定值将链表分割成两部分，一部分节点的值小于基准值，另一部分节点的值大于等于基准值。

链表重排方法链表重排可以使用迭代或递归方法实现。下面详细介绍几种常见的链表重排序类型及其代码实现。

1. 链表反转

1.1 迭代法迭代法使用三个指针：`prev`， `curr` 和 `next`。`curr` 指向当前节点，`prev` 指向 `curr` 的前一个节点，`next` 指向 `curr` 的下一个节点。算法的基本思想是：1. 初始化 `prev` 为 `null`，`curr` 为链表头节点。 2. 迭代遍历链表，每次迭代执行以下步骤：* 将 `next` 指向 `curr` 的下一个节点。* 将 `curr` 的 `next` 指针指向 `prev`，反转当前节点的指向。* 将 `prev` 指向 `curr`，`curr` 指向 `next`，移动到下一个节点。 3. 返回 `prev`，它现在指向反转后链表的头节点。**代码示例 (Python):**```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head: ListNode) -> ListNode:prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nextreturn prev ```

1.2 递归法递归法利用递归函数的调用栈来反转链表。基本思想是：1. 递归到链表的最后一个节点，将其作为反转后链表的头节点。 2. 在递归返回的过程中，反转当前节点与其后继节点之间的指向。**代码示例 (Python):**```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverseList(head: ListNode) -> ListNode:if not head or not head.next:return headnew_head = reverseList(head.next)head.next.next = headhead.next = Nonereturn new_head ```

2. 奇偶链表奇偶链表重排序可以使用两个指针 `odd` 和 `even` 分别指向奇数和偶数节点。基本思想是：1. 初始化 `odd` 指向头节点，`even` 指向头节点的下一个节点。 2. 迭代遍历链表，每次迭代执行以下步骤：* 将 `odd.next` 指向 `even.next`。* 将 `odd` 指向 `odd.next`。* 将 `even.next` 指向 `odd.next`。* 将 `even` 指向 `even.next`。 3. 最后将 `odd.next` 指向 `even_head`，连接奇数链表和偶数链表。 4. 返回原始链表的头节点。**代码示例 (Python):**```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef oddEvenList(head: ListNode) -> ListNode:if not head or not head.next:return headodd = headeven = head.nexteven_head = evenwhile even and even.next:odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.nextodd.next = even_headreturn head ```

3. 指定基准分割指定基准分割可以使用两个指针 `smaller` 和 `larger` 分别指向小于和大于等于基准值的节点。基本思想是：1. 创建两个虚拟节点 `smaller_head` 和 `larger_head` 分别作为小于和大于等于基准值的链表的头部。 2. 初始化 `smaller` 指向 `smaller_head`，`larger` 指向 `larger_head`。 3. 迭代遍历链表，根据当前节点的值将其连接到 `smaller` 或 `larger` 指针的后面。 4. 最后将 `smaller.next` 指向 `larger_head.next`，连接两个链表。 5. 返回 `smaller_head.next`，即分割后小于基准值的链表的头节点。**代码示例 (Python):**```python class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef partition(head: ListNode, x: int) -> ListNode:smaller_head = ListNode(0)larger_head = ListNode(0)smaller = smaller_headlarger = larger_headwhile head:if head.val < x:smaller.next = headsmaller = smaller.nextelse:larger.next = headlarger = larger.nexthead = head.nextsmaller.next = larger_head.nextreturn smaller_head.next ```

总结链表重排是链表操作中的常见问题，可以通过迭代和递归方法实现。理解不同类型的链表重排方法，并根据具体需求选择合适的算法，对于提高代码效率和解决实际问题至关重要。