//////////////////////////////////////
//  <算法 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指向的节点
  //(偶数节点)放到链表末尾
    }
}

评论