【算法题】重排链表

这题要求的是对链表重新排序，让原来：→→……→→ 的链表变成 →→→→→…… ，也就是链表后面的节点每隔一个插入到前面。

因为是单链表，没法从后往前遍历，我们可以先把链表的节点全部存储到一个栈中，然后再把栈中一半的节点插入到前面，步骤如下图所示。

    public void reorderList(ListNode head) {
        // 先把节点全部存储到栈中
        Stack<ListNode> stk = new Stack<>();
        ListNode cur = head;
        while (cur != null) {
            stk.push(cur);
            cur = cur.next;
        }
        // 从头节点开始，把栈中的节点每隔一个插入到链表中。
        int cnt = (stk.size() + 1) / 2;
        cur = head;// cur节点，栈中的节点要插入到它的后面
        while (cnt-- > 0) {
            ListNode next = cur.next;// 记录cur的下一个节点
            cur.next = stk.pop();// 栈中的节点出栈，插入到cur节点的后面。
            if (cnt != 0)
                cur.next.next = next;// cur->next就是出栈的节点
            else // 如果后半部分已经插入完了，最后一个节点的next指向空。
                cur.next.next = null;
            cur = next;// 更新cur节点，继续插入。
        }
    }

public:
    void reorderList(ListNode *head) {
        // 先把节点全部存储到栈中
        stack<ListNode *> stk;
        ListNode *cur = head;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        // 从头节点开始，把栈中的节点每隔一个插入到链表中。
        int cnt = (stk.size() + 1) / 2;
        cur = head;// cur节点，栈中的节点要插入到它的后面
        while (cnt-- > 0) {
            ListNode *next = cur->next;// 记录cur的下一个节点
            cur->next = stk.top();// 栈顶节点插入到cur节点的后面。
            stk.pop();// 栈顶节点出栈。
            if (cnt != 0)
                cur->next->next = next;// cur->next就是出栈的节点
            else // 如果后半部分已经插入完了，最后一个节点的next指向空。
                cur->next->next = nullptr;
            cur = next;// 更新cur节点，继续插入。
        }
    }

各大厂算法面试题已经整理好了，请看这里：《算法专栏》