学步园

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}.

题目解析：

题目非常简单，先将链表分成两半，将后半段翻转，然后将两个链表合并就行了。

但是实现的时候各种错误。链表的问题，就是比较繁琐，各种细节。一定要动手画清楚才行。

class Solution {
public:
    void reorderList(ListNode *head) {
        if(head == NULL)
            return ;
        int n = 1;
        ListNode *p = head;
        while(p->next){
            n++;
            p = p->next;
        }
        if(n==1 || n==2)
            return ;

        int i = 1;
        p = head;
        while(i < n/2){
            i++;
            p = p->next;
        }
        ListNode *q = p->next;
        p->next = NULL;
        p = ReverseList(q);
        MergeList(head,p);
    }
    ListNode *ReverseList(ListNode *head){
        ListNode *p = head;
        ListNode *q = p->next;
        p->next = NULL;
        while(q){
            ListNode *h = q->next;
            q->next = p;
            p = q;
            q = h;
        }
        head = p;
        return head;
    }
    ListNode *MergeList(ListNode *head,ListNode *q){
        ListNode *p = head;
        while(p->next){
            ListNode *h = p->next;
            p->next = q;
            p = h;
            h = q->next;
            q->next = p;
            q = h;
        }
        p->next = q;
        return head;
    }
};

关于链表的翻转，上面用的是非递归方法。也可以用递归方式，代码也确实有点意思，值得参考。

public ListNode recursive_reverse(ListNode head) {
    if(head == null || head.next==null)
        return head;
    return recursive_reverse(head, head.next);
}
private ListNode recursive_reverse(ListNode current, ListNode next) 
{
    if (next == null) return current;
    ListNode newHead = recursive_reverse(current.next, next.next);
    next.next = current;
    current.next = null;
    return newHead;
}