143. 重排链表
查看题目中等
链表
高频
解法一：迭代法
时间复杂度：O(n) | 空间复杂度：O(n) | 推荐使用
动画演示
准备就绪 - 输入链表值（用逗号分隔），然后点击开始
代码实现
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
List<ListNode> list = new ArrayList<ListNode>();
ListNode node = head;
while (node != null) {
list.add(node);
node = node.next;
}
int i = 0, j = list.size() - 1;
while (i < j) {
list.get(i).next = list.get(j);
i++;
if (i == j) {
break;
}
list.get(j).next = list.get(i);
j--;
}
list.get(i).next = null;
}
}时间复杂度：O(n)
空间复杂度：O(n)
将链表节点存储到数组中，使用双指针i和j分别指向数组开头和结尾，交替连接节点，最后将末尾节点的next置为null。这种方法的时间复杂度为O(n)，空间复杂度为O(n)。