结合两个双重链接列表(Combine Two Doubly Linked List)
优质
小牛编辑
128浏览
2023-12-01
实现 (Implementation)
该算法的实现如下 -
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *prev;
struct node *next;
};
struct node *list = NULL;
struct node *list_last = NULL;
struct node *even = NULL;
struct node *even_last = NULL;
struct node *odd = NULL;
struct node *odd_last = NULL;
struct node *current = NULL;
//Create Linked List
void insert(int data) {
// Allocate memory for new node;
struct node *link = (struct node*) malloc(sizeof(struct node));
link->data = data;
link->prev = NULL;
link->next = NULL;
// If head is empty, create new list
if(data%2 == 0) {
if(even == NULL) {
even = link;
return;
} else {
current = even;
while(current->next != NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
even_last = link;
link->prev = current;
}
} else {
if(odd == NULL) {
odd = link;
return;
} else {
current = odd;
while(current->next!=NULL)
current = current->next;
// Insert link at the end of the list
current->next = link;
odd_last = link;
link->prev = current;
}
}
}
//display the list
void print_backward(struct node *head) {
struct node *ptr = head;
printf("\n[last] <=>");
//start from the beginning
while(ptr != NULL) {
printf(" %d <=>",ptr->data);
ptr = ptr->prev;
}
printf(" [head]\n");
}
//display the list
void printList(struct node *head) {
struct node *ptr = head;
printf("\n[head] <=>");
//start from the beginning
while(ptr != NULL) {
printf(" %d <=>",ptr->data);
ptr = ptr->next;
}
printf(" [last]\n");
}
void combine() {
struct node *link;
list = even;
link = list;
while(link->next!= NULL) {
link = link->next;
}
link->next = odd;
odd->prev = link;
// assign link_last to last node of new list
while(link->next!= NULL) {
link = link->next;
}
list_last = link;
}
int main() {
int i;
for(i = 1; i <= 10; i++)
insert(i);
printf("Even : ");
printList(even);
printf("Even (R): ");
print_backward(even_last);
printf("Odd : ");
printList(odd);
printf("Odd (R) : ");
print_backward(odd_last);
combine();
printf("Combined List :\n");
printList(list);
printf("Combined List (R):\n");
print_backward(list_last);
return 0;
}
输出 (Output)
该方案的产出应该是 -
Even :
[head] <=> 2 <=> 4 <=> 6 <=> 8 <=> 10 <=> [last]
Even (R):
[last] <=> 10 <=> 8 <=> 6 <=> 4 <=> 2 <=> [head]
Odd :
[head] <=> 1 <=> 3 <=> 5 <=> 7 <=> 9 <=> [last]
Odd (R) :
[last] <=> 9 <=> 7 <=> 5 <=> 3 <=> 1 <=> [head]
Combined List :
[head] <=> 2 <=> 4 <=> 6 <=> 8 <=> 10 <=> 1 <=> 3 <=> 5 <=> 7 <=> 9 <=> [last]
Combined List (R):
[last] <=> 9 <=> 7 <=> 5 <=> 3 <=> 1 <=> 10 <=> 8 <=> 6 <=> 4 <=> 2 <=> [head]