leetCode-143:Reorder List

问题描述

给定一个链表，用 L0→L1→…→Ln-1→Ln 表示，要求在不改变节点值的情况下将链表改成以下顺序：L0→Ln→L1→Ln-1→L2→Ln-2→…。题目链接：**点我**

样例输入输出

输入：1->2->3->4

输出：1->4->2->3

输入：1->2->3->4->5

输出：1->5->2->4->3

问题解法

此题最简单的解法就是遍历一遍，在遍历过程中用一个数组来存储每个节点，然后遍历数组中的节点，根据规则将每个节点的 next 指针指向对应节点即可。但是这种做法需要花费 O(n) 的空间复杂度。一般而言，leetcode 上链表的题目，都是用 O(1) 的空间复杂度进行求解的。针对此题，一种 O(1)的空间复杂度的解法如下：

• 首先将链表对半拆分，拆成两个子链表。可以用快慢指针进行拆分，时间复杂度为 O(n)，空间复杂度为 O(1)

• 其次，对后半部分的链接进行倒序。时间复杂度为 O(n)，空间复杂度为 O(1)

• 最后，合并前后两个子链表。时间复杂度为 O(n)，空间复杂度为 O(1)

总体而言，时间复杂度为 O(n)，空间复杂度为 O(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)
    {
        if (head == null || head.next == null)
        {
            return;
        }

        // split the list
        ListNode half = head;
        ListNode next = head;
        ListNode prevEnd = head;
        while (next != null && next.next != null)
        {
            next = next.next.next;
            prevEnd = half;
            half = half.next;
        }
        prevEnd.next = null;

        // reverse the post half list
        ListNode postHead = reverseList(half);

        // merge two half list
        mergeList(head, postHead);
    }

    private void mergeList(ListNode firstHead, ListNode secondHead)
    {
        ListNode first = firstHead;
        ListNode second = secondHead;
        while (first != null && first.next != null)
        {
            ListNode secondNext = second.next;
            second.next = first.next;
            first.next = second;
            first = second.next;
            second = secondNext;
        }
        first.next = second;
    }

    private ListNode reverseList(ListNode head)
    {
        ListNode dummyNode = new ListNode(-1, head);
        while (head.next != null)
        {
            ListNode next = head.next;
            head.next = next.next;
            next.next = dummyNode.next;
            dummyNode.next = next;
        }

        return dummyNode.next;
    }
}