Leetcode系列之链表（1）

1.题目

将给定的单链表L： L 0→L 1→…→L n-1→L n,重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…

要求使用原地算法，并且不改变节点的值

例如：

对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.

思路：

1.找出中点，拆分列表（利用快慢指针）

2.中点后的链表反转（链表的翻转）

3.按要求合并链表（链表的合并）

代码：

/**

* Definition for singly-linked list.

* class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) {

*        val = x;

*        next = null;

*    }

* }

*/

public class Solution {

    public void reorderList(ListNode head) {

        if(head == null || head.next == null)

            return;

        // 找中点

        ListNode mid = findMiddle(head);

        // 中点后的链表反转

        ListNode rev = reverse(mid);

        // 两个链表合并

        merge(head,rev);

    }

    private static ListNode findMiddle(ListNode head){

        ListNode slow = head;

        ListNode fast = head;

        while(fast.next != null && fast.next.next != null){

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

    private static ListNode reverse(ListNode cur){

        ListNode pre = null;

        ListNode next = cur;

        while(next != null){

            next = cur.next;

            cur.next = pre;

            pre = cur;

            cur = next;

        }

        return pre;

    }

    private static void merge(ListNode head, ListNode rev){

        ListNode headNext = null;

        ListNode revNext = null;

        while(head != null && rev != null){

            headNext = head.next;

            revNext = rev.next;

            head.next = rev;

            rev.next = headNext;

            head = headNext;

            rev = revNext;

        }

    }

}