【LeetCode·中等】143. 重排链表（reorder-list）题目描述 描述 给定一个单链表 L **的头节点

题目描述

描述

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

L(0) → L(1) → … → L(n - 1) → L(n)

请将其重新排列后变为：

L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 2) → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

示例 2：

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

提示：

• 链表的长度范围为 [1, 5 * 10(4)]
• 1 <= node.val <= 1000

地址

leetcode.cn/problems/re…

解题方法

方法1⃣️：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        ListNode left = head;
        ListNode right = head;
        ListNode rightPre = head;
        int count = 1;
        while (true) {
            if (right==null || right.next == null) {
                return;
            }
            while (right.next != null) {
                count++;
                rightPre = right;
                right = right.next;
            }
            if(count < 3){
                return;
            }
            right.next = left.next;
            left.next = right;
            rightPre.next = null;
            left = right.next;
            right = left.next;
        }
    }
}

复杂度分析

时间复杂度：O(n^2)，其中 n是链表的长度

空间复杂度：O(1)，无需额外的空间

方法2⃣️：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
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)，其中 n是链表的长度

空间复杂度：O(n)，需额外的线性表空间

总结

方法1⃣️是比较直观的一种解法，但是由于单链表只能从前向后寻找，所以每次都要获取到当前最后一个节点就需要每次从当前节点向后遍历，因此时间复杂度约为O(n^2)，方法2⃣️是在方法1⃣️的基础上进行了优化，即通过List（线性表）将所有节点进行存储，以便在获取的时候不用再次遍历，于是将是时间复杂度优化到了O(n)，但是由于额外创建了一个跟链表长度一致的线性表，因此空间复杂度从O(1)增大到了O(n)