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

### 数据结构知识点详解 #### 一、单链表 单链表是一种常见的线性数据结构，其中每个元素（节点）包含一个数据域和一个指向下一个元素的指针。本章节将详细探讨与单链表相关的典型算法问题及其解决方案。 #### 1. 单链表反转 **目的**: 将单链表中的节点顺序颠倒过来。 **算法1** (迭代法): - **思路**: 通过额外的两个指针 `next` 和 `nextnext` 来保存当前节点的下一个节点和下下一个节点的信息。 - **核心代码**: ```csharp public static Link ReverseLink1(Link head) { Link curr = head.Next; Link next = null; Link nextnext = null; if (curr == null || curr.Next == null) // 如果链表为空或者只有一个节点 { return head; } while (curr.Next != null) { next = curr.Next; // 1. 保存当前节点的下一个节点 nextnext = next.Next; // 2. 保存下一个节点的下一个节点 next.Next = head.Next; // 3. 下一个节点的指针指向原链表的第一个节点 head.Next = next; // 4. 链表的头节点的指针指向下一个节点 curr.Next = nextnext; // 5. 当前节点的指针指向原来保存的下一个节点的下一个节点 } return head; } ``` **算法2** (递归法): - **思路**: 使用递归来反转链表。首先反转剩下的链表部分，然后修改当前节点的指针指向。 - **核心代码**: ```csharp public static Link ReverseLink3(Link head) { if (head.Next == null || head.Next.Next == null) // 如果链表为空或者只有一个节点 { return head; } head.Next = ReverseLink(head.Next); // 为递归产生的逆序链表添加一个空表头 return head; } static Link ReverseLink(Link head) { if (head.Next == null) { return head; } Link rHead = ReverseLink(head.Next); // 递归反转剩下的链表 head.Next.Next = head; // 修改当前节点的指针指向 head.Next = null; // 断开与原始链表的连接 return rHead; } ``` #### 2. 找出单链表的倒数第4个元素 **目的**: 在不预先知道链表长度的情况下找出倒数第4个元素。 **思路**: 使用双指针技巧。设置两个指针，初始时第二个指针比第一个指针多前进3个节点。当第二个指针到达链表尾部时，第一个指针正好指向倒数第4个元素。 **核心代码**: ```csharp public static string FindFourthFromEnd(Link head) { if (head == null || head.Next == null) { return "Invalid input"; } Link first = head.Next; Link second = head.Next; for (int i = 0; i < 3; i++) { if (second.Next != null) { second = second.Next; } else { return "Not enough elements"; } } while (second.Next != null) { first = first.Next; second = second.Next; } return first.Data; } ``` #### 3. 找出单链表的中间元素 **目的**: 找出单链表的中间元素，若链表长度为奇数，则返回中间那个元素；若为偶数，则返回靠右的那个中间元素。 **思路**: 使用快慢指针技巧。设置两个指针，快指针每次移动两步，慢指针每次移动一步。当快指针到达链表尾部时，慢指针正好指向中间位置。 **核心代码**: ```csharp public static string FindMiddleElement(Link head) { if (head == null || head.Next == null) { return "Invalid input"; } Link slow = head.Next; Link fast = head.Next; while (fast.Next != null && fast.Next.Next != null) { slow = slow.Next; fast = fast.Next.Next; } if (fast.Next == null) { return slow.Data; } else { return slow.Next.Data; } } ``` #### 4. 删除无头单链表的一个节点 **目的**: 给定一个单链表和其中一个节点的指针，删除该节点。 **思路**: 由于没有头节点，可以通过修改待删除节点的数据和指针来间接删除该节点。 **核心代码**: ```csharp public static void DeleteNode(Link node) { if (node == null || node.Next == null) { return; } node.Data = node.Next.Data; node.Next = node.Next.Next; } ``` #### 5. 两个不交叉的有序链表的合并 **目的**: 合并两个已排序的单链表，使得结果链表依然有序。 **思路**: 创建一个新的链表，并按照升序顺序依次插入两个链表中的节点。 **核心代码**: ```csharp public static Link MergeTwoSortedLists(Link list1, Link list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } Link result; if (list1.Data <= list2.Data) { result = list1; result.Next = MergeTwoSortedLists(list1.Next, list2); } else { result = list2; result.Next = MergeTwoSortedLists(list1, list2.Next); } return result; } ``` 以上介绍了几个典型的单链表算法问题及其解决方法。这些算法不仅在实际开发中有广泛的应用，也是面试中的常见考点。理解并掌握这些算法可以帮助开发者更好地理解和设计数据结构，提高程序的性能。