剑指offer刷题笔记六：从尾到头打印链表（前导文章之一文搞懂C++单向链表）

飞熊 • 2023年4月6日下午12:54 • 后端笔记 • 阅读 166

注：本文是对链接: 剑指offer刷题笔记六：从尾到头打印链表（正式）.的前导说明，意在简要说明链表的基本内含。

学习是循序渐进的过程，以下从主要五个方面，初步介绍链表结构:

链表的定义

struct ListNode {
	int m_nValue;
	ListNode* m_pNext;
};

链表主要由两部分构成，数据部分和指针部分，数据代表本结点的数据值，指针表示下一个结点。
2. 链表的创建

ListNode* CreateListNode(int value) {
	ListNode* pNode = new ListNode();
	pNode->m_nValue = value;
	pNode->m_pNext = nullptr;

	return pNode;
}

创建结点时，首先给定一个数据值，作为参数传入，然后将指针部分初始化为nullptr。
3. 链表的连接

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext) {
	if (pCurrent == nullptr)//判断当前结点是否有效
	{
		printf("Error to connect two nodes.\n");
		exit(1);
	}

	pCurrent->m_pNext = pNext;
}

链表的连接操作其实就是更改结点的指针部分的地址，将两个两个的结点连接起来。使得前一个结点的指针指向后一个结点的地址。（很容易发现，最后一个结点的指针部分将为nullptr）
4. 链表的打印

void PrintList(ListNode* pHead)
{
	printf("PrintList starts.\n");

	ListNode* pNode = pHead;//创建一个新的结点，避免修改链表
	while (pNode != nullptr)
	{
		printf("%d\t", pNode->m_nValue);
		pNode = pNode->m_pNext;
	}

	printf("\nPrintList ends.\n");
}

从链表头开始，通过“pNode”变量来访问每一个结点，并将其通过while打印输出。
5. 链表的销毁

void DestroyList(ListNode* pHead)
{
    ListNode* pNode = pHead;
    while(pNode != nullptr)
    {
        pHead = pHead->m_pNext;
        delete pNode;
        pNode = pHead;
    }
}

通过变量“pNode”来储存当前结点的地址，然后进行“pHead”的移动，“pHead”移动成功后，此时pHead已指向下一个结点了，删除“pNode”所指向空间的内存，然后继续给pNode赋值…照此循环。

最后再来看一看，主函数中链表的使用：

int main()
{
    std::cout << "Test begins!\n";
    ListNode* pNode1 = CreateListNode(1);
    ListNode* pNode2 = CreateListNode(2);
    ListNode* pNode3 = CreateListNode(3);//创建结点

    ConnectListNodes(pNode1, pNode2);
    ConnectListNodes(pNode2, pNode3);//连接结点
    
    PrintList(pNode1);//打印链表
    DestroyList(pNode1);//销毁链表
}