算法大全-面试题-数据结构.docx

【链表基础与操作】 链表是一种数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用。在C#中，我们可以创建一个简单的链表节点类`Link`，如下所示： ```csharp public class Link { public Link Next; public string Data; public Link(Link next, string data) { this.Next = next; this.Data = data; } } ``` 链表的遍历通常通过一个指针（在C#中可以称为`curr`）从头节点开始，逐个访问每个节点的数据，直到遇到null为止： ```csharp Link head = GenerateLink(); Link curr = head; while (curr != null) { Console.WriteLine(curr.Data); curr = curr.Next; } ``` **1. 单链表反转** 反转链表的两种常见方法是迭代和递归。 - **迭代法**（算法1）： 这种方法通过三个辅助变量`curr`、`next`和`nextnext`来实现。在遍历过程中，不断地更新节点的next指针，使其指向前一个节点，直到遍历结束。注意处理特殊情况，即链表为空或只有一个元素。 ```csharp public static Link ReverseLink1(Link head) { // ... 代码省略 ... } ``` - **递归法**（算法2&3）： 递归法首先将链表逆序输出，然后进行反转。递归时，先处理子链表，再处理当前节点。在实际反转链表时，需要在递归调用后处理反转的逻辑，以确保链表的正确连接。 ```csharp public static void ReverseLink2(Link head) { // ... 代码省略 ... } public static Link ReverseLink3(Link head) { // ... 代码省略 ... } ``` **2. 链表操作** 链表操作还包括其他各种问题，如： - **找倒数第k个元素**：可以使用双指针，一个指针先向前移动k步，然后两个指针同时移动，当先移动的指针到达末尾时，另一个指针即指向倒数第k个元素。 - **找中间元素**：快慢指针法，快指针每次移动两步，慢指针每次移动一步，当快指针到达末尾时，慢指针就在中间。 - **删除节点**：需要知道前一个节点，通过改变前一个节点的next指针指向当前节点的下一个节点。 - **合并有序链表**：从头节点开始，比较两个链表当前节点的值，将较小的节点添加到结果链表，然后移动较小节点的指针。 - **二级链表转一级链表**：遍历一级链表，对于每个节点，遍历其对应的二级链表，将二级链表的节点添加到一级链表的末尾。 - **交换链表中任意两个元素**：需要找到要交换的两个节点，以及它们的前一个节点，然后调整next指针。 - **判断链表是否有环**：快慢指针法，快指针每次移动两步，慢指针每次移动一步，如果快慢指针相遇则有环。 - **找到环的起始点**：使用两个指针，一个快指针从相遇点开始，一个慢指针从头开始，当它们相遇时，相遇点就是环的起始点。 - **计算环的长度**：从相遇点开始，计数器加1，直到再次到达环的起始点，计数器的值就是环的长度。 - **判断两个链表是否相交**：计算两个链表的长度，让长度长的链表先走差值步数，然后两个指针同时移动，若相遇则相交。 - **找到相交点**：同上，两个指针同时移动，相遇点即为相交点。 - **链表模拟大整数加法**：将链表视为数字，逐位相加，处理进位。 - **链表排序**：可以使用归并排序或插入排序等算法对链表进行排序。 - **删除重复元素**：遍历链表，比较当前节点和下一个节点的值，若相同则删除下一个节点。 以上就是链表相关的一些基本概念和操作，这些知识在面试中经常出现，对于理解和掌握数据结构至关重要。