题解 | #重排链表#

重排链表

http://www.nowcoder.com/practice/3d281dc0b3704347846a110bf561ef6b

算法思想一：数组

解题思路：

因为链表不支持下标访问，所以我们无法随机访问链表中任意位置的元素。
因此比较容易想到的一个方法是，我们利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。

算法步骤：

1、初始化空数组res，遍历链表将链表结点存储到数组中

2、设置双指针i，j

按照题目，res[i].next = res[j]，指针 i 加1

再拼接 res[j] 结点， res[j].next = res[i], 指针 j 减1

循环到 i >= j 跳出循环

代码展示：

Python版本

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 
# @param head ListNode类 
# @return void
#
class Solution:
    def reorderList(self , head ):
        # write code here
        if not head:
            return
        # 初始化数组
        res = []
        node = head
        while node:
            res.append(node)
            node = node.next
        # 进行链表结点交换
        i, j = 0, len(res) - 1
        while i < j:
            res[i].next = res[j]
            i += 1
            if i == j:
                break
            res[j].next = res[i]
            j -= 1
        # 指明最后
        res[i].next = None

复杂度分析：

时间复杂度O(N)：N是链表的结点数量，遍历链表、数组构建新链表

空间复杂度O(N)：使用额外的数组空间

算法思想二：寻找链表中点 + 链表逆序 + 合并链表

解题思路：

1、找中点的话，可以使用快慢指针。快指针一次走两步，慢指针一次走一步，当快指针走到终点的话，慢指针会刚好到中点。如果节点个数是偶数的话，slow 走到的是左端点，利用这一点，我们可以把奇数和偶数的情况合并，不需要分开考虑。
2、链表逆序的话，参考 https://blog.nowcoder.net/n/d259b250747b4085bc7975f102d248c4
3、合并链表，两个指针分别向后移动就可以。

图解：

链表：{1，2，3，4，5，6}

步骤	操作	链表
1	寻找链表中点，将链表分为两半	{1，2，3} {4，5，6}
2	将后半链表反转	{1，2，3} {6，5，4}
3	合并两个链表	{1，6，2，5，3，4}

输出链表：{1，6，2，5，3，4}

代码展示：

JAVA版本

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
        return;
    }
    //找中点，链表分成两个
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode newHead = slow.next;
    slow.next = null;
    
    //第二个链表倒置，反转后半部分链表
    newHead = reverseList(newHead);
    
    //链表节点依次连接
    while (newHead != null) {
        ListNode temp = newHead.next;
        newHead.next = head.next;
        head.next = newHead;
        head = newHead.next;
        newHead = temp;
    }
}

    private ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tail = head;
        head = head.next;
        tail.next = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = tail;
            tail = head;
            head = temp;
        }
        return tail;
    }
}