C语言机试经典例题链表

### C语言链表机试经典例题 以下是几个经典的C语言链表机试题目及其解析： #### 1. 单链表反转 单链表反转是一个非常常见的面试题，其核心在于调整节点之间的指针方向。 ```c struct ListNode { int val; struct ListNode *next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev = NULL; struct ListNode *curr = head; while (curr != NULL) { struct ListNode *nextTemp = curr->next; // 记录下一个节点 curr->next = prev; // 当前节点指向前面的节点 prev = curr; // 前面的节点向前移动一步 curr = nextTemp; // 当前节点向后移动一步 } return prev; // 返回新的头结点 } ``` 此代码实现了单链表的原地反转功能[^4]。 --- #### 2. 合并两个有序链表 给定两个升序排列的链表，将其合并成一个新的升序链表。 ```c struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ struct ListNode dummyHead = {0}; struct ListNode* tail = &dummyHead; while(l1 && l2){ if(l1->val < l2->val){ tail->next = l1; l1 = l1->next; }else{ tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummyHead.next; } ``` 这段代码利用了一个虚拟头节点来简化边界条件处理，并逐步比较两链表中的元素大小完成合并操作[^5]。 --- #### 3. 删除倒数第N个节点 删除链表中倒数第 N 个节点，假设 N 的值有效。 ```c struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ struct ListNode dummyHead = {0}, *first = &dummyHead, *second = &dummyHead; dummyHead.next = head; for(int i=0;i<=n;i++) first = first->next; while(first){ first = first->next; second = second->next; } second->next = second->next->next; return dummyHead.next; } ``` 该算法采用双指针法解决这个问题，先让第一个指针前进 `n` 步，再同步推进两个指针直到到达终点[^6]。 --- #### 4. 判断链表是否有环 判断一个链表是否存在环结构。 ```c bool hasCycle(struct ListNode *head) { if (!head || !head->next) return false; struct ListNode *slow = head; struct ListNode *fast = head; while(fast && fast->next){ slow = slow->next; fast = fast->next->next; if(slow == fast) return true; } return false; } ``` 上述方法基于快慢指针的思想实现。如果存在环，则快慢指针最终会相遇；否则快指针会率先抵达链表末端[^7]。 --- ###