LeetCode之单链表重排序

问题描述

Given a singly linked list L: L 0→L 1→…→L n-1→L n,
reorder it to: L 0→L n →L 1→L n-1→L 2→L n-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given{1,2,3,4}, reorder it to{1,4,2,3}.

题目要求

• 时间限制：1秒

• 空间限制：32768K

解题思路

两个游标：一个用来指向下一次将要插入元素的位置，另一个用来遍历链表。从根结点开始遍历，如果当前节点的next节点不为空并且next的next节点不为空，则取最后一个节点插入到当前节点之后，游标一跳两个位置。直到游标一节点的next节点为空或者next的next节点为空。

代码实现

package com.reorder.list;

import com.sort.linkedlist.ListNode;

/**
 * @author [email protected]
 * @since 2018/11/17 下午4:01
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null) {
            return;
        }
        if (head.next == null || head.next.next == null) {
            return;
        }
        ListNode pt = head;
        ListNode index = head;
        ListNode preIndex = head;
        while (pt.next != null && pt.next.next != null) {
            while (index.next != null) {
                preIndex = index;
                index = index.next;
            }
            preIndex.next = null;
            index.next = pt.next;
            pt.next = index;
            pt = pt.next.next;
        }
    }
}

这种方法可行，但是每排序一个节点都需要遍历一次链表，效率比较低，可以看到下图，运行时间较长，占用内存已经 超过空间限制 了。

参考

看了一下网上给出的方案，几乎都是一样的：

这道链表重排序问题可以拆分为以下三个小问题：

1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。

2. 将第二个链翻转。

3. 将第二个链表的元素间隔地插入第一个链表中。

都是将链表拆成两个独立的链表进行重排序。

剽窃来的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;这道链表重排序问题可以拆分为以下三个小问题：

1. 使用快慢指针来找到链表的中点，并将链表从中点处断开，形成两个独立的链表。

2. 将第二个链翻转。

3. 将第二个链表的元素间隔地插入第一个链表中。
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if (!head || !head->next || !head->next->next) return;
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *mid = slow->next;
        slow->next = NULL;
        ListNode *last = mid;
        ListNode *pre = NULL;
        while (last) {
            ListNode *next = last->next;
            last->next = pre;
            pre = last;
            last = next;
        }
        while (head && pre) {
            ListNode *next = head->next;
            head->next = pre;
            pre = pre->next;
            head->next->next = next;
            head = next;
        }
    }
};

时间空间使用都很少，性能问题没了。