#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
typedef int Elemtype;

typedef struct LNode {
    Elemtype data;
    struct LNode *next;
} LNode, *LinkList;

// 双链表定义，核心性质，L->prior指向尾元素，尾元素->next指向头结点；
typedef struct DNode {
    Elemtype data;
    int freq;
    struct DNode *prior, *next;
} DNode, *DLinkList;

void InitList(LinkList *L) {
    (*L) = (LNode *)malloc(sizeof(LNode));
    (*L)->next = NULL;
}

void HeadInsert(LinkList *L) {
    LNode *s;   int x;
    while (scanf("%d", &x) && x != -1) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = (*L)->next;
        (*L)->next = s;
    }
}

void PrintList(LinkList *L) {
    LNode *p = (*L)->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}

// WD T11 判断循环双链表是否对称：
int Symmetry(DLinkList *L) {    // 此处的节点是否对称取决于节点的data是否相同；
    DNode *p = (*L)->next, *q = (*L)->prior;
    while (p != q && p->next != q) {
        if (p->data == q->data) 
            p = p->next, q = q->prior;
        else return 0;
    }
    return 1;
}

// WD T13：
DNode *Locate(DLinkList *L, Elemtype x) {
    DNode *p = (*L)->next, *q;
    // 寻找p节点
    while (p && p->data != x) p = p->next;
    if (!p) exit(0);
    p->freq ++;
    // 特殊情况
    if (p->prior == (*L) && p->prior->freq > p->freq) return p;
    // 非特殊情况下修改p前驱与后继的指向
    if (p->next != NULL) p->next->prior = p->prior;
    p->prior->next = p->next;
    // 非特殊情况下根据freq将p放置到指定位置
    q = p->prior;
    while (q != (*L) && q->freq <= p->freq) q = q->prior;
    p->next = q->next;
    q->next->prior = p;
    p->prior = q;
    q->next = p;
    return p;
}

// WD T14 带头结点的循环右移；
void CycleRMove(LinkList *L, int k) {
    LNode *p = (*L), *tail;
    int l = 0, dl;
    while (p->next != NULL) l ++, p = p->next;
    if (k != 0 && k != l) {
        tail = p, dl = l - k, p = (*L);
        while (dl --) p = p->next;
        tail->next = (*L)->next;
        (*L)->next = p->next;
        p->next = NULL;
    }
}

// WD T15 寻找链表环的入口点；
LNode *FindLoopStart(LinkList *L) {
    LNode *slow = (*L), *fast = (*L);
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }
    if (fast == NULL || fast->next == NULL) return NULL;
    slow = (*L);
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
}

// WD T16 求单链表最大孪生和 (不带头结点)；
int PairSum(LinkList L) {       // 不修改L链表，因此拷贝复制一份；
    if (L == NULL) return -1;
    LNode *slow = L, *fast = L->next, *p, *r;
    while (fast->next != NULL) slow = slow->next, fast = fast->next->next;     // 偶数个节点的性质；
    // 右侧节点链表逆置；
    p = slow->next;
    slow->next = NULL;
    while (p != NULL) {
        r = p->next;
        p->next = slow->next;
        slow->next = p;
        p = r;
    }
    int ms = 0, ts;
    slow = L;
    while (fast != NULL) {
        ts = slow->data + fast->data;
        ms = ts > ms ? ts : ms;
        slow = slow->next, fast = fast->next;
    }
    return ms;
}

// WD T17 求倒数第k个节点的data（一次遍历，双指针法，p先移动k次，然后令q指向头节点，两者同速率移动，直到p指向NULL）；
int FindK(LinkList *L, int k) {
    LNode *p = (*L), *q = (*L);
    while (p != NULL && k != 0) p = p->next, k --;
    if (p == NULL) return 0;
    while (p != NULL) p = p->next, q = q->next;
    printf("%d\n", q->data);
    return 1;
}

// WD T19 空间换时间 - 数组模拟哈希表；
int _abs(int a) { return a > 0 ? a : -a; }
void del_abs_same(LinkList *L, int n) {
    int *mp = (int *)malloc((n + 1) * sizeof(int));
    memset(mp, 0, (n + 1) * sizeof(int));
    LNode *pre = (*L), *p = pre->next;
    while (p != NULL) {
        if (mp[_abs(p->data)]) {
            pre->next = p->next;
            free(p);
            p = pre->next;
        }
        else {
            mp[_abs(p->data)] = 1;
            pre = p, p = p->next;
        }
    }
}

// WD T20 快慢指针 + 链表逆置 + 链表合并；
void Rearrange(LinkList *L) {
    if ((*L)->next == NULL) return;
    LNode *slow = (*L)->next, *fast = slow->next, *p, *q;
    while (fast != NULL && fast->next != NULL) slow = slow->next, fast = fast->next->next;
    p = slow->next;
    slow->next = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = slow->next;
        slow->next = p;
        p = q;
    }
    fast = slow->next, slow->next = NULL, slow = (*L)->next;    // 需置前半段链表的尾结点next指向为NULL，否则形成环，造成TL；
    while (fast != NULL) {
        p = slow->next, q = fast->next;
        slow->next = fast, fast->next = p;
        slow = p, fast = q;
    }
}

int main() {
    LinkList Head;  InitList(&Head);  HeadInsert(&Head);
    // printf("%d", PairSum(Head->next));      // 测试样例：8 7 6 5 3 2 -1 --> 11
    Rearrange(&Head);
    PrintList(&Head);
    return 0;
}