////////////////////////////////////////  <算法 i~iv> //  //  Exercise : 3.35  , Page : 75////  exercises description://   编写一个函数,重新排列一个链表.使偶数位置的节点集中到链表后半部分,奇数位置节点集中// 到链表前半部分,同时分别使奇数位节点和偶数位节点之间的顺序保持不变.////  zhaoyg  2008.1.22////////////////////////////////////// #include <iostream>using namespace std; struct list{    int content;    list * next;}; void fun (list * head); int main(){    list *head = NULL,*current,*temp;    int value;        cout << "enter value,q to quit\n";        while (cin >> value)    {        if (head==NULL)            current = head = new list;        else        {            current->next = new list;            current = current->next;        }                current->next = NULL;        current->content = value;    }     fun(head);     current = head;        while( current != NULL)    {  cout << current ->content<<" ";  current=current->next;    }  //free memory  temp = current = head; while (current!=NULL) {  temp=current->next;  free(current);  current=temp; }        system("pause");    return 0;} void fun (list *head){    list *mark,*end,*current=head;   // using pointer mark to mark last node of the original list,  // and the pointer end aways point to the actual last node        while (current->next!=NULL)    current=current->next ;  //point to the last node        mark=end=current;  //make mark and end point to last node        current=head;   //reset current point to head        while (1)    {        end->next = current->next ;  //将当前的下一个节点,即偶数位,赋给end        end = end->next;    //指向最后一个节点        current->next = current->next->next;  //从原始链表中删除掉赋给end的节点  end->next = NULL;        current = current->next;         if (current==mark || end==mark)            break;  //current==mark表示链表节点个数为奇数;end==mark则表示为偶数个,且此时已将market指向的节点  //(偶数节点)放到链表末尾    }}

评论