链表环检测与反转算法详解

在数据结构面试中，链表是常见的考察对象，面试者可能会针对其特性提出各种问题。本篇文章聚焦于两个关键的链表操作：判断链表是否存在环以及链表反转。 首先，**判断链表是否存在环**是一项经典问题。这个问题可以通过使用双指针法解决。创建两个指针`p1`和`p2`，初始时让它们都指向链表头`head`。`p1`每次前进一步，`p2`前进两步。如果链表中存在环，那么`p2`最终会与`p1`相遇（环的入口）。如果遍历完整个链表，`p2`都没有遇到`NULL`或与`p1`重合，那么链表无环；否则，链表中有环。提供的C++代码展示了这种实现方式： ```cpp bool IsLoop(link* head) { link* p1 = head, *p2 = head; if (head == NULL || head->next == NULL) { return false; } do { p1 = p1->next; p2 = p2->next->next; } while (p2 && p2->next && p1 != p2); return p1 == p2; } ``` 接下来是**链表反转**，它涉及到对单向链表元素顺序的改变。最直观的方法是采用迭代的方式，创建三个指针`pre`（前一个节点）、`cur`（当前节点）和`ne`（下一个节点）。遍历过程中，依次将`cur`的`next`指向前一个节点`pre`，然后更新`pre`、`cur`和`ne`的指向。最后，将头节点`head`的`next`置为`NULL`，并将其指向下个非空节点。代码示例如下： ```cpp void reverse(linka*& head) { if (head == NULL) return; linka* pre = head, *cur = head->next; while (cur) { linka* ne = cur->next; cur->next = pre; pre = cur; cur = ne; } head->next = NULL; head = pre; } ``` 另一种方法是递归反转，但需要注意递归结束后最后一个节点会形成一个环，因此需要在递归返回时确保其`next`域为`NULL`。由于涉及到改变`head`指针，使用引用传递参数更为方便。递归版的反转算法代码如下： ```cpp linka* reverse(linka* p, linka*& head) { if (p == NULL || p->next == NULL) { return p; } linka* next = reverse(p->next, head); p->next->next = p; p->next = NULL; return next; } ``` 总结起来，这两个问题涵盖了链表基础操作中的重要知识点：环形链表检测，展示了使用迭代和递归方法；以及单向链表反转，演示了迭代和递归的实现策略。掌握这些技巧对于理解链表数据结构以及在面试中展示编程能力至关重要。