有序双循环链表的插入 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

有序双循环链表的插入, 须要找到插入位置, 能够採用, 两个指针, 一个在前, 一个在后.

保证前面的小于等于插入值, 后面的大于等于插入值.

特殊情况, 首尾插入(大于或小于整个链表)或单节点, 推断条件为后指针指向首节点. 则须要直接插入.

插入链表头, 须要调整链表头节点.

代码22行.

代码:

/* * main.cpp * *  Created on: 2014.9.18 *      Author: Spike *//*eclipse cdt, gcc 4.8.1*/#include 
     
      #include 
      
       using namespace std;struct ListNode {	ListNode (int v) {		value = v;		prev = NULL;		next = NULL;	}	int value;	ListNode* prev;	ListNode* next;};ListNode* CreateLists() {	ListNode* head = new ListNode(0);	ListNode* node1 = new ListNode(1);	ListNode* node2 = new ListNode(2);	ListNode* node4 = new ListNode(4);	ListNode* node5 = new ListNode(5);	head->prev = node5;	head->next = node1;	node1->prev = head;	node1->next = node2;	node2->prev = node1;	node2->next = node4;	node4->prev = node2;	node4->next = node5;	node5->prev = node4;	node5->next = head;	return head;}ListNode* CreateLists2() {	ListNode* head = new ListNode(0);	head->prev = head;	head->next = head;	return head;}void Print(ListNode* head) {	ListNode* node = head;	printf("%d ", node->value);	node = node->next;	while (node != head) {		printf("%d ", node->value);		node = node->next;	}	printf("\n");}ListNode* InsertNode(ListNode* head, ListNode* node) {	if (head == NULL || node == NULL)		return head;	ListNode* prevNode = head;	ListNode* nextNode = head->next;	while(1) {		if ((prevNode->value < node->value &&				nextNode->value >= node->value)				|| (nextNode == head))		{			prevNode->next = node;			node->prev = prevNode;			nextNode->prev = node;			node->next = nextNode;			if (node->value < head->value) {				head = node;			}			break;		}		prevNode = prevNode->next;		nextNode = prevNode->next;	}	return head;}int main (void){	ListNode* head = CreateLists();	Print(head);	ListNode* node = new ListNode(3);	ListNode* newList = InsertNode(head, node);	Print(newList);	return 0;}
      
     

输出:

0 1 2 4 5 0 1 2 3 4 5