Even and odd linked list
2018-08-29 本文已影响9人
Tedisaname
Even and odd list
Given a single linked list, put all the odd and even nodes together. Note >that the odd and even nodes here refer to the parity of the node number, >not the parity of the value of the node.
// C codes:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h> //function to exit()
#define OK 1 //status for 1
#define ERROR 0 //status for 0
//struct for a node
typedef struct Node{
int data;
struct Node * next;
}Node,*PNode;
// Function to the linked list initialization
int Initialization(PNode& head)
{
head = (PNode)malloc(sizeof(Node));//create a head Node
head->next = NULL;//initialize the head node
return OK;
}
//crerate the linked list from user input
void create(PNode head)
{
int m,a;
PNode p, q;
printf("Please input the length of the linked list:");
scanf("%d",&m);
q = NULL;
for(int i = 0; i < m; i++)
{
scanf("%d",&a);
p = (PNode)malloc(sizeof(Node));
p->data = a;
p->next = NULL;
if(head->next == NULL)//attention!!!!head ->next == NULL ,not head == NULL
head->next = p;//head directly points to p if the head points to NULL
else
q->next = p;//else,pointer q points to the p;
q = p;//pointer q points to p
}
}
//print all the emements of linked list
void printLinkedlist(PNode head)
{
PNode t = head->next;//the next field of the head pointer is the first valid node attention~!!!!!!
while(t != NULL)
{
printf("%d ",t->data);
t = t->next;
}
printf("\n");
}
//Function to get the length of the linked list
int getlength(PNode head)
{
int k = 0;
PNode t = head->next;
while(t != NULL)
{
k++;
t = t->next;
}
return k;
}
//Function to the even and odd linked list
PNode evenOddList(PNode A,PNode result,int len)
{
int j = 1;
PNode p,q,w;
p = A->next;
q = NULL;
while(p != NULL && j <= len)
{
if(j % 2 == 1)
{
PNode w = (PNode)malloc(sizeof(Node));
w->data = p->data;
w->next = NULL;
if(result->next == NULL)
result->next = w;
else
q->next = w;
q = w;
}
j++;
p = p->next;
}
j = 1;
p = A->next;
while(p != NULL && j <= len)
{
if(j % 2 == 0)
{
PNode w = (PNode)malloc(sizeof(Node));
w->data = p->data;
w->next = NULL;
if(result->next == NULL)
result->next = w;
else
q->next = w;
q = w;
}
j++;
p = p->next;
}
return result;
}
int main()
{
PNode A,result;//create two nodes of two linked list A and result
if(Initialization(A)){
printf("Initialization successful!\n");
}
else
{
printf("Initialization failed!\n");
exit(ERROR);
}
create(A);//Create linked list from the function to user input
printLinkedlist(A);//print list before sorting
int len = getlength(A);//get the length of the linked list
printf("the length of the linked list is %d\n",len);
if(Initialization(result)){
printf("Initialization successful!\n");
}
else
{
printf("Initialization failed!\n");
exit(ERROR);
}
evenOddList(A,result,len);//Function is called to create the even and odd linked list
printLinkedlist(result);//print the linked list of the even and
return 0;
}
driver data to test:
input: 1->2->3->4->5->NULL
output: 1->3->5->2->4->NULL
You can leave me a message if you find out anything incorrect in my diary, I'll correct it, thanks.