Reorder List (Medium)

Description

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

Analysis

感觉写烦了= =。哎。。思维不好。只能这么乱搞。
先从中间分开。然后将后半部分链表逆置。然后模拟连接即可

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//C++
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    int getlength(ListNode *head){
        int len = 0;
        while(head){
            len ++;
            head = head->next;
        }
        return len;
    }
    ListNode* rev(ListNode *head){
        ListNode *p,*q ,*t=NULL;
        while(head){
            p = head;
            q = head->next;
            p->next = t;
            head = q;
            t = p;
        }
        return p;
    }
public:
    void reorderList(ListNode *head) {
        if(head==NULL||head->next==NULL)
            return;
        ListNode *p = head,*q = head,*t;
        int n = getlength(head);
        if(n == 2)
            return;
        int len = 0;
        while(p){
            len++;
            if(len==n/2)
                break;
            p = p->next;
        }
        t = p->next;
        p->next = NULL;
        q = rev(t);
        for(int i=0;i<n/2;i++){
            p = head->next;
            t = q->next;
            head->next = q;
            if(i==(n/2-1))  break;
            q->next = p;
            q = t;
            head = p;
        }
    }
};