链表操作

转自：http://blog.csdn.net/ojshilu/article/details/12222035
题目：已知链表L0->L1->L2->L3->.......->Ln-1->Ln-2->Ln.将该链表变为L0->Ln->L1->Ln-1->...................
分析：分析变化后的链表和给出的原链表关系，看出将链表平分为2段，将后半部分反转，之后按照顺序穿插即可。
别人的源码：

#include <iostream>
#include <malloc.h>
using namespace std;

typedef struct node
{
    int val;
    node* next;
}node,*list;

void displaylist(list s)
{
    while(s!=NULL)
    {
        cout<<s->val<<" ";
        s = s->next;
    }
    cout<<endl;
}

int main()
{
    int a[] = {9,8,7,6,5,4,3,2,1};
    //创建原始链表
    list L=NULL;
    for(int i=0;i<sizeof(a)/sizeof(int);i++)
    {
        node *p = (node*)malloc(sizeof(node));
        p->val = a[i];
        p->next = L;
        L = p;
    }
    //非常重要的边界特殊情况检查
    if(L==NULL)
        return -1;

    displaylist(L);

    //寻找中间结点位置
    node *fast=L,*slow=L;
    while(fast->next!=NULL && fast->next->next!=NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    node *mid = slow->next;
    slow->next = NULL; //正式将原链表一切为二

    //将后半部分链表反转
    list s2 = NULL;
    node *tmp;
    while(mid!=NULL)
    {
        tmp = mid->next;
        mid->next = s2;
        s2 = mid;
        mid = tmp;
    }
    //displaylist(L);
    //displaylist(s2);

    //交叉合并两个链表
    list s1 = L;
    while(s2!=NULL)
    {
        tmp = s2->next;
        s2->next = s1->next;
        s1->next = s2;
        s1 = s1->next->next;
        s2 = tmp;
    }
    displaylist(L);
    return 1;
}