文章目录

• 1.题目描述
• 2.思路
• • 2.1 代码
  • 2.2 测试结果
• 3.总结

1.题目描述

重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

示例 2：

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

2.思路

2.1 代码

从题目中可以看到，重排序后的链表后半部分将会倒序链上，因此考虑使用栈来进行操作。首先将整个链表入栈，然后使用一个 index 表示当前重排序的链表序号，从 0 开始。

• 如果 index 为偶数，表示当前元素为正序排列的链表，则从栈中弹出栈顶元素，让当前节点的 next 指向弹出元素，弹出元素的 next 指向当前节点的原 next 节点
• 如果 index 为奇数，则不对当前节点进行操作

当处理完链表的每个节点之后，进行最后一个节点的处理

• 当链表节点总数数为偶数时，curr 指向最后一个节点， curr.next = null
• 当链表节点总数数为奇数时，curr 指向最后一个节点的前一个节点，curr.next.next = null

class Solution {    public void reorderList(ListNode head) { if (head.next == null) {     return; } ListNode curr = head; ListNode[] stack = new ListNode[50000]; int index = -1; while (curr != null) {     stack[++index] = curr;     curr = curr.next; } curr = head; int i = 0; int count = index+1; while (i < count) {     if (i % 2 == 0) {  ListNode next = curr.next;  curr.next = stack[index--];  curr.next.next = next;     }     curr = curr.next;     i++; } if (count % 2 == 0) {     curr.next = null; } else {     curr.next.next = null; }    }}

2.2 测试结果

通过测试

3.总结

• 使用栈来进行解答
• 间隔将栈顶元素弹出并设置为 next 节点
• 遍历完成之后处理尾节点，链表节点总数为偶数，当前节点的 next 指向null；为奇数，当前节点的下一个节点为尾节点，curr.next.next = null