数据结构面试之二——双向链表表、循环链表、有序链表的常见操作
题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。
二、双向链表
双向链表的建立是在单链表的基础上，多了一个指向前驱的指针back。其他的操作类似，注意点就是在双向链表的操作，尤其插入、删除操作中需要修改两个指针的指向，一个是back指针，一个是next指针。
1.双向链表的构建【前面插入】
构建双向链表注意点：1）修改first指针（头指针）的指向。2）修改back、next指针。
//反向表头插入，从前面插入...
template<typename Type>
nodeType<Type>*doublyLinkedList<Type>::buildListBackward()
{
nodeType<Type> *newNode;
int num;
cout << " Enter a list of integer end with -999." << endl;
cin >> num;
while(num != -999)
{
//..add
newNode = new nodeType<Type>;
newNode->info = num;
newNode->next = NULL;
newNode->back = NULL;
if(first == NULL)
{
first = newNode;
}
else
{
newNode->next = first;
first->back = newNode;
first = newNode;
}
cin >> num;
}
return first;
}
2.双向链表的插入节点【此处考虑插入后保证有序，直接插入排序】
节点的插入同单链表，依然需要考虑多种因素。分以下几类：
1）双向链表为空，“提示信息”并返回。
2）双向链表非空，待插入节点的元素值小于first节点，需要修改first指针。
3）双向链表非空，待插入节点的元素值为链表中间的节点，需修改back、next指向。
4）双向链表非空，待插入节点在最末尾节点以后，修改最末节点的指针。
//双向不循环链表
template<typename Type>
voiddoublyLinkedList<Type>::insertNode(const Type& insertItem) //new
{
nodeType<Type> *current;
nodeType<Type> *trailCurrent;
nodeType<Type> *newNode;
bool found = false;
newNode = new nodeType<Type>;
newNode->info = insertItem;
newNode->next = NULL;
newNode->back = NULL;
//case 1: 空表
if(first == NULL)
{
first = newNode;
}
else
{
current = first;
while( current != NULL)
{
if( current->info >= insertItem )
{
found = true;
break;
}
else
{
trailCurrent = current;
current = current->next;
}
}
//case 2: 第一个节点
if(current == first)
{
current->next = newNode;
newNode->back = current;
}
else
{
//case 3: 中间节点
if(current != NULL)
{
newNode->next = trailCurrent->next;
current->back = newNode;
trailCurrent->next = newNode;
newNode->back = trailCurrent;
}
else //case 4:最后一个节点前
{
trailCurrent->next = newNode;
newNode->back = trailCurrent;
}//end case 4
}
}
}
3.双向链表的删除节点
同样需要考虑以下几点：
1） 链表为空，“提示信息”并返回。
2） 链表非空，查找删除的元素在链表是否存在。是的话，found=true；否的话，found=false。
3） 如果没有找到包含查找元素的节点，“错误提示”并返回。
4） 如果找到，主要节点位置。如果是头节点或末尾节点主要修改first指针，及节点的back、next指向；如果不是头节点或者末尾节点就是中间节点，主要back、next的指向，完成插入。
template<typename Type>
void doublyLinkedList<Type>::deleteNode(constType& deleteItem) //new
{
nodeType<Type> *current = new nodeType<Type>;
nodeType<Type> *trailCurrent;
bool found = false;
//case 1: 空表
if(first == NULL)
{
cout << "The List is NULL!" << endl;
exit(1);
}
else
{
current = first;
while( current != NULL)
{
if( current->info == deleteItem )
{
found = true;
break;
}
else
{
trailCurrent = current;
current = current->next;
}
}
if(found)
{
//case 2: 第一个节点
if(current == first)
{
first = current->next;
delete current;
}
else
{
//case 3: 中间节点
if(current != NULL)
{
if(current->next != NULL) //case3.1:要删除的是中间节点.
{
trailCurrent->next =current->next;
current->next->back = trailCurrent;
delete current;
}
else
{
trailCurrent->next = NULL;//case3.2:要删除的为最后一个节点.
delete current;
}
}
}// end else
}// end if
else
{
cout << "The elem " <<deleteItem << " is not Exist in the List!" << endl;//case 4: 链表中无此节点.
}
}//end else
}//end
三、循环链表
循环链表能保障从每一个节点出发都能检索链表。即：last指针的指向不再为空，而是指向了first（头结点）。
循环链表在构建链表、查找元素、插入、删除、操作中要注意修改末尾节点指针的指向，保证链表的循环。
1. 前插式构建循环链表
【思路】：每次在first指针前面插入节点；插入每个节点后注意修改last->link的指向。
template<typename Type>
void cycleList<Type>::bulidCycListBackward() //前插构造循环链表.
{
Type newItem;
while(cin >> newItem, newItem != -999)
{
nodeType<Type>* newNode = newnodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL)
{
first = newNode;
last = newNode;
first->link = first;
last->link = first;
}
else
{
newNode->link = first;
last->link = newNode;
first = newNode;
}
}
cout << "输入完毕!" << endl;
}
2. 循环链表插入元素[后插入]
【思路】：同构造循环链表，每次在last指针后面插入节点；插入每个节点后注意修改last->link的指向。
//只在last末尾插入
template<typename Type>
voidcycleList<Type>::insertCycList(const Type& newItem)
{
nodeType<Type> *newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL) //链表为空...
{
first = newNode;
last = newNode;
first->link = first;
last->link = first;
}
else //链表非空...
{
last->link = newNode;
newNode->link = first;
last = newNode;
}
cout << newItem << "was inserted!" <<endl;
}
3. 删除循环链表节点
考虑到是否为空链表、删除元素在链表中不存在、及节点存在（节点的位置可能为共分头、中间、尾），所以分为以下5种情况分别处理。:
//case1:链表为空。
//case2:链表非空，删除节点为头节点。
//case3:链表非空，删除节点为尾节点。
//case4:链表非空，删除节点为中间节点。
//case5:链表非空，不存在=deleteItem的节点。
template<typename Type>
voidcycleList<Type>::delCycList(const Type& deleteItem)
{
nodeType<Type> *current = new nodeType<Type>;
nodeType<Type> *trailCurrent = new nodeType<Type>;
nodeType<Type> *temp ;
bool found = false;
if( first == NULL )
{
cout << "The List is Empty!" << endl;//case1
return;
}
if( first->info == deleteItem ) //case2
{
temp = new nodeType<Type>;
temp = first;
first = first->link;
last->link = first;
cout << "The node has" << deleteItem<< " was deleted! " << endl;
delete temp;
return;
}
else //cas3,case4.需要查找后定位。
{
current = first->link;
while( !found && current != first)
{
if( current->info == deleteItem )
{
found = true;
break;
}
else
{
trailCurrent = current;
current = current->link;
}
}// end while
if(found)
{
temp = new nodeType<Type>;
if(current == last) //case3
{
temp = last;
trailCurrent->link = last->link; //last->link = first
last = trailCurrent;
}
else
{
temp = current;
trailCurrent->link= current->link;
}
cout << "The Elem : " <<deleteItem << " was deleted! " << endl;
delete temp;
}
else
{
cout << "The Elem : " <<deleteItem << " was not Exist in the List! " << endl;
}
}//end else
}
四、有序链表
注意：此处有序链表无非是在之前的一、单链表的操作的基础上，在插入元素的时候，按顺序插入，考虑的排序。
为了体现有序的特点，特通过递归实现了有序链表的逆序打印。关于有序链表或者链表的非递归实现，可以通过栈实现。下一节会分析并实现。
1. 有序链表的插入
考虑以下三种情况：
1） 当前链表为空；
2） 当前链表非空，要插入的元素值小于头结点的元素值；
3） 当前链表非空，要插入的元素值大于头结点的元素值，可以考虑找到第一个大于其的元素则停止搜索，插入其前即可。
template<typename Type>
void orderedLinkedListType<Type>::insertNode(constType& newItem)
{
nodeType<Type>* current;
nodeType<Type>* trailCurrent;
nodeType<Type>* newNode;
bool found = false;
newNode = new nodeType<Type>;
newNode->info = newItem;
newNode->link = NULL;
if(first == NULL) //case1：链表为空.
{
first = newNode;
last = first;
}
else
{
current = first;
while( !found && current != NULL) //循环查找
{
if(current->info >= newItem)
{
found = true;
break;
}
else
{
trailCurrent = current;
current = current->link;
}
}//end while
//first 特殊处理..
if(current == first) //case2：新插入的元素小于first节点的元素值..
{
newNode->link = first;
first = newNode;
}
else //其他..
{
newNode->link = current; //case3：新插入的节点在非first位置
trailCurrent->link = newNode;
}
}//end else
}
2. 递归实现有序链表的逆序打印
template<typename Type>
voidorderedLinkedListType<Type>::printListReverse() const //逆序打印.
{
reversePrint(first);
cout << endl;
}
//递归实现单链表的逆序打印.
template<typename Type>
voidorderedLinkedListType<Type>::reversePrint(nodeType<Type>* current)const //逆序打印
{
if(current != NULL)
{
reversePrint(current->link);
cout << current->info << "\t";
}
}
