链表面试题全攻略：从基础到进阶

"链表是计算机科学中的基础数据结构，经常在编程面试中被用作考察面试者基础能力和编码技能的工具。由于链表操作涉及指针，而指针的使用容易出错，因此链表题目在面试中具有很高的价值。本文提供了一系列常见的链表面试题及其详细解答，旨在帮助求职者准备面试。" 链表是一种非连续存储的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用。在C语言中，链表节点通常定义如下： ```c struct ListNode { int m_nKey; // 数据域 ListNode* m_pNext; // 指向下一个节点的指针 }; ``` 以下是一些经典的链表面试题及其解法： 1. **求单链表中结点的个数**：通过遍历链表，计数器每次增加1，直到达到链表末尾。时间复杂度为O(n)。 ```c unsigned int GetListLength(ListNode* pHead) { if (pHead == NULL) return 0; unsigned int nLength = 0; ListNode* pCurrent = pHead; while (pCurrent != NULL) { nLength++; pCurrent = pCurrent->m_pNext; } return nLength; } ``` 2. **将单链表反转**：遍历链表，每次迭代时将当前节点的`m_pNext`指向前一个节点，然后移动指针。时间复杂度为O(n)。 ```c ListNode* ReverseList(ListNode* pHead) { if (pHead == NULL || pHead->m_pNext == NULL) return pHead; ListNode* pReversedHead = NULL; // 反转后的新链表头 ListNode* pCurrent = pHead; while (pCurrent != NULL) { ListNode* pTemp = pCurrent->m_pNext; pCurrent->m_pNext = pReversedHead; pReversedHead = pCurrent; pCurrent = pTemp; } return pReversedHead; } ``` 3. **查找单链表中的倒数第K个结点**：可以使用双指针法，先让一个指针先走K步，然后两个指针同步移动，直到先走的指针到达链表末尾，另一个指针所指向的节点就是目标节点。时间复杂度为O(n)。 4. **查找单链表的中间结点**：同样可以使用双指针，一个指针每次走一步，另一个指针每次走两步，当快指针到达末尾时，慢指针即在中间位置。时间复杂度为O(n)。 5. **从尾到头打印单链表**：可以通过反向遍历链表，或者在遍历过程中逆序存储节点，然后依次输出。时间复杂度为O(n)。 6. **已知两个单链表pHead1和pHead2各自有序，把它们合并成一个链表依然有序**：可以比较两个链表的节点值，将较小的节点添加到结果链表，直至其中一个链表为空。时间复杂度为O(n + m)，n和m分别为两个链表的长度。 7. **判断一个单链表中是否有环**：Floyd判环算法，使用两个指针，快指针每次走两步，慢指针每次走一步，若两者相遇则有环。时间复杂度为O(n)。 8. **判断两个单链表是否相交**：分别找到两个链表的尾部，如果它们相等，则链表相交；否则不相交。时间复杂度为O(n + m)。 9. **求两个单链表相交的第一个节点**：首先找到两个链表的长度差，然后让长度较长的链表先走长度差的步数，之后两个指针同步移动，直到相遇的节点就是相交点。时间复杂度为O(n + m)。 10. **已知一个单链表中存在环，求进入环中的第一个节点**：快慢指针法，当快指针追上慢指针时，它们相遇在环内。再从相遇点开始，以相同速度向环内移动，最终相遇点即为入环点。时间复杂度为O(n)。 11. **给出一单链表头指针pHead和一节点指针pToBeDeleted，O(1)时间复杂度删除节点pToBeDeleted**：需要修改pToBeDeleted前一个节点的`m_pNext`指针指向pToBeDeleted的下一个节点，然后释放pToBeDeleted。为了实现O(1)的时间复杂度，需要维护一个额外的指针指向pToBeDeleted的前一个节点。 这些题目涵盖了链表操作的基本技巧，理解和熟练掌握这些解题方法对于面试至关重要。在实际面试中，面试官可能会对这些基础题目进行变种，考察面试者的思维灵活性和问题解决能力。因此，深入理解链表及其操作是成为优秀程序员的基础。