博客

单链表通过结构体表示

struct ListNode
{
	int data;
	ListNode* next;
	ListNode(int data) {
		this->data = data;
		this->next = nullptr;
	}
};
typedef ListNode* List;

大数阶乘的函数

思路：链表的每一个结点存储一个3位数的值，每次从头结点开始进位与计算，其他的和乘法一样，最后处理结果时，如果某一结点的值不是三位数需要在前面补0补成三位数

string Solution::bigNumFactorial(int n)
{
	string result = "";

	List num = new ListNode(n);
	List temp;

	while (n >= 2) { // n = 2 之后进入循环只需要处理进位就行了
		n--;
		// 调整进位
		temp = num;
		while (temp != nullptr) {
			if (temp->data > 999) {
				if (temp->next == nullptr) {
					temp->next = new ListNode(temp->data / 1000);
				}
				else {
					temp->next->data += temp->data / 1000;
				}
				temp->data = temp->data % 1000;
			}
			temp = temp->next;
		}
		temp = num;
		// 进行计算
		while (temp != nullptr) {
			temp->data *= n;
			temp = temp->next;
		}
	}

	string tempStr;

	while (num != nullptr) {
		tempStr = to_string(num->data);
		// 如果不到三位数就补0
		while (tempStr.size() < 3) {
			tempStr = "0" + tempStr;
		}
		result = tempStr + result;
		num = num->next;
	}

	// 去掉结果最前面的0
	while (result[0] == '0') {
		result .erase(result.begin());
	}

	return result;
}

2021/11/15 简单修改了一下

#include <string>
#include <cmath>

using std::string;

const int kDIGIT = 3;
const int kMOD = [](int digit) {
	int ans = 1;
	while (digit-- > 0) {
		ans *= 10;
	}
	return ans;
}(kDIGIT);

struct ListNode {
	int data;
	ListNode* next;
	ListNode(int data_ = int(), ListNode* next_ = nullptr)
		: data(data_), next(next_) {}
};

std::string list2StdString(ListNode* head) {
	string result = "";

	while (head != nullptr) {
		string tempStr = std::to_string(head->data);
		// 如果不到三位数就补0
		while (tempStr.size() < kDIGIT) {
			tempStr = "0" + tempStr;
		}
		result = tempStr + result;
		head = head->next;
	}

	// 去掉结果最前面的0
	while (result[0] == '0') {
		result.erase(result.begin());
	}

	return result;
}

std::string bigNumFactorial(int n) {
	ListNode* node = new ListNode(n);

	// n = 2 之后进入循环只需要处理进位就行了
	while (n-- >= 2) {
		// 调整进位
		for (ListNode* temp = node; temp != nullptr; temp = temp->next) {
			if (temp->data > 999) {
				if (temp->next == nullptr) {
					temp->next = new ListNode(temp->data / kMOD);
				}
				else {
					temp->next->data += temp->data / kMOD;
				}
				temp->data = temp->data % kMOD;
			}
		}
		// 进行计算
		for (ListNode* temp = node; temp != nullptr; temp = temp->next) {
			temp->data *= n;
		}
	}

	return list2StdString(node);
}