博客

题意：


有一个整数元素建立的单链表A，设计一个算法，将其拆分成两个链表A 和B，使得链表A中含有所有偶数的结点，B链表中含有所有的奇数结点。

且保持原来的相对次序。

单链表的存储结构：

typedef struct LinkList{
        int data;
        LinkList * next;
    }

分析：


这里采用新建链表的方法，而题意要求

保持相对次序

，所以这里采用

尾插法建立单链表

。

这里可以用原来的单链表A的头结点作为新链表的头结点。所有不用再生成一个新头结点。

思路：


1.定义一个遍历单链表A的指针p,两个尾指针 ra,rb，要生成一个头结点。

2.将尾指针赋值好。头结点也是。

3.通过while循环，条件为p != null ，在循环中，判断是否为偶数，如果是偶数，将该数插入链表A中，再后移，如果是奇数，则插入链表B中，再后移。

4.最后两个链表的最后一个节点都置为空。

C代码实现：

 void Splist(LinkList * &A, LinkList * &B){
        LinkList * P = A->next,*ra,*rb;  //遍历链表的指针p.两个尾指针。
        ra = A;
        B = (LinkList *)malloc(sizeof(LinkList));
        rb = B;
        while(p!=null){
            if(p->data%2 == 0){   //偶数结点
                ra->next = p;
                ra = p;
                p = p->next;
            }else{               //奇数结点
                rb->next = p;
                rb = p;
                p = p->next;
            }
        }
        ra->next = rb->next = null; //两尾节点指针域置为空。  
    }