【leetcode】No.143：reorder-list

题目描述

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.

input:

Given
{1,2,3,4}

output:

reorder it to
{1,4,2,3}

思路：

把两边分成前与后两段，后面一段需要逆序，然后两个链表进行合并，链表拆分可以使用快慢指针，后面一段链表逆序可以使用头插法构造

代码：

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        ListNode tmp = divide(head);
        merge(head, tmp);
    }

    // 快慢指针法划分成两个链表，一个正序，一个反序
    ListNode divide(ListNode head){
        ListNode slow = head;
        ListNode quick = head;
        while (quick.next != null && quick.next.next != null){
            slow = slow.next;
            quick = quick.next.next;
        }
        ListNode pre = slow,cur = pre.next,post;
        pre.next = null;
        ListNode tmp = new ListNode(0);
        while (cur != null){
            post = cur.next;
            cur.next = tmp.next;
            tmp.next = cur;
            cur = post;
        }
        return tmp;
    }

    // 合并两个链表
    void merge(ListNode head, ListNode tmp){
        ListNode cur = head;
        ListNode insert = tmp.next;
        while (insert != null){
            tmp.next = insert.next;
            insert.next = cur.next;
            cur.next = insert;
            cur = insert.next;
            insert = tmp.next;
        }
    }
}