限制长度双向链表的插入操作

    面试遇到的问题，一开始面试官是问我有什么方案可以实现排行榜，当时给出了两个方案。后面面试官又在我的其中一种方案上让我手写代码实现排序双线链表的插入，根据score值插入，并且链表长度限制在100。

    需要考虑的点：1）插入在链表表头的；2）插入到链表表尾；3）插入到链表中间；4）需要在遍历整个链表的时候统计链表的长度；5）如果长度刚好在100而插入刚好在末尾，则此时不需要执行插入操作。完整代码如下

#include <iostream>

using namespace std;

#define MAX_RANK 100

struct Link {
	int score;
	int uid;
	Link* prev;
	Link* next;
	Link() {
		score = 0;
		uid = 0;
		prev = NULL;
		next = NULL;
	}
};

Link* initLink(int n) {
	if (n <= 0) {
		return NULL;
	}
	int i = n;
	Link *head = new Link;
	head->score = i * 2;
	Link *node = head;
	while (i > 1) {
		i--;
		node->next = new Link;
		node->next->score = i * 2;
		node->next->prev = node;
		node = node->next;
	}
	return head;
}

void freeLink(Link *L) {
	Link *node = NULL;
	while (L) {
		node = L->next;
		delete L;
		L = node;
	}
}

Link* insertLinkLimit(Link* L, int score) {
	if (L == NULL) {
		L = new Link;
		L->score = score;
		return L;
	}
	int cnt = 1;
	Link *head = L, *tmp = L->next;
	if (L->score <= score) {
		// 插入链表头
		head = new Link;
		head->score = score;
		head->next = L;
		L->prev = head;
		cnt++;
	}
	else {
		while (tmp && L->score >= score && tmp->score >= score) {
			// 寻找非插入链表头时的插入位置
			L = tmp;
			tmp = tmp->next;
			cnt++;
		}
		if (tmp == NULL && cnt == MAX_RANK) {
			// 刚好是要直接插到第MAX_RANK+1即满链表的尾部，
			// 此时不插入，直接返回。
			return head;
		}
		// 其他情况执行插入操作
		// 1）在链表中间
		// 2）在链表末尾但是插入后长度没有超过限制
		L->next = new Link;
		L->next->score = score;
		L->next->next = tmp;
		L->next->prev = L;
		if (tmp) {
			tmp->prev = L->next;
		}
		L = L->next;
		cnt++;
	}
	// 因为需要统计长度，所以执行插入操作后还需要遍历链表
	while (tmp && cnt < MAX_RANK) {
		tmp = tmp->next;
		L = L->next;
		cnt++;
	}
	// 如果插入后操作长度限制，则需要删除最后一个节点。
	if (tmp) {
		delete tmp;
		L->next = NULL;
	}
	cout << cnt << endl;
	return head;
}

void printLink(Link* L) {
	while (L) {
		cout << L->score << " ";
		L = L->next;
	}
	cout << endl;
}

int main() {
	Link *L = initLink(10);
	L = insertLinkLimit(L, 111);
	printLink(L);
	freeLink(L);
	return 0;
}

      简单的测试了几种情况，输出都是对的。