Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.

先将后半部分linkedlistreverse一下,然后再将两个list合并即可,注意如果是奇数个数的话,前一个list多一个
1,2,3,4,5,6,7 -> 1, 2, 3, 4, 7, 6, 5 -> 1, 7, 2, 6, 3, 5, 4

先找到mid,用一个fast和一个slow,每个fast先step,check不是null以后,slow和fast再往前step,这样偶数个情况的话slow是取前一个值。
然后将后半个和前半个list拆开以后,将后半个list reverse,用两个pointer step即可。
最后将两个list合并,用两个pointer,每次两个pointer都往前step1步,将三个node连起,知道第二个pointer是null为止。

/**
 * 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 = findMid(head);
        ListNode s1 = head;
        ListNode s2 = reverseList(mid.next);
        mid.next = null;
        while(s2 != null)
        {
            ListNode n = s1.next;
            s1.next = s2;
            s1 = n;
            n = s2.next;
            s2.next = s1;
            s2 = n;
        }
    }
    
    public ListNode findMid(ListNode head)
    {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null)
        {
            fast = fast.next;
            if (fast == null)
                break;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    
    
    public ListNode reverseList(ListNode head)
    {
        ListNode pre = null;
        while(head != null)
        {
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}

第二次的code (未测试)

/**
 * 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 || head.next.next == null)
            return;
        ListNode n = findMid(head);
        ListNode l2 = n.next;
        n.next = null;
        l2 = reverseList(l2);
        head = mergeList(head, l2);
    }
    
    public ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null) {
            fast = fast.next;
            if (fast.next == null)
                break;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    
    public ListNode reverseList(ListNode head) {
        ListNode curr = head.next;
        ListNode result = head;
        while(curr != null) {
            ListNode temp = curr.next;
            curr.next = result;
            result = curr;
            curr = temp;
        }
        return result;
    }
    
    public ListNode mergeList(ListNode h1, ListNode h2) {
        ListNode c1 = h1;
        ListNode c2 = h2;
        while(c2 != null) {
            ListNode temp1 = c1.next;
            ListNode temp2 = c2.next;
            c1.next = c2;
            c2.next = temp1;
            c1 = temp1;
            c2 = temp2;
        }
        return h1;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s