单链表合并与逆序：递归与非递归实现

本文主要介绍了如何使用非递归和递归方法合并两个有序的单链表，以及如何将单链表逆序。 在数据结构中，单链表是一种常见的线性数据结构，其中每个节点包含数据和指向下一个节点的指针。在处理有序链表时，合并和逆序是两个常见的操作。 ### 非递归合并单链表 非递归合并两个有序升序排列的单链表涉及到比较两个链表的元素并适当插入。关键在于找到合适的位置将较短链表的节点插入到较长链表中，以保持整体的有序性。以下是一个实现该操作的函数： ```cpp node* t_node(node* head, node* item) { node* p = head; node* q = NULL; // 指向 p 之前的节点 while (p->data < item->data && p != NULL) { q = p; p = p->next; } if (p == head) { // 插入到原头结点之前 item->next = p; return item; } else { // 插入到 p 与 q 之间 q->next = item; item->next = p; } return head; } node* merge(node* head1, node* head2) { node* head; // 合并后的头指针 node* p; node* nextp; // 指向 p 之后 if (head1 == NULL) { // 一个链表为空返回另一个链表 return head2; } else if (head2 == NULL) { return head1; } if (length(head1) >= length(head2)) { // 使用 length() 函数计算链表长度 head = head1; p = head2; } else { head = head2; p = head1; } while (p != NULL) { nextp = p->next; head = t_node(head, p); p = nextp; // 指向要插入的下一个节点 } return head; } ``` 这个函数首先判断哪个链表更长，然后逐个从较短的链表中取出节点并插入到较长链表的适当位置。 ### 递归合并单链表 递归方法同样适用于合并两个有序链表。基本思想是从两个链表的头部开始比较，将较小的节点放入结果链表，然后递归地处理剩余部分。以下是一个递归实现： ```cpp node* merge_recursive(node* head1, node* head2) { if (head1 == NULL) { return head2; } else if (head2 == NULL) { return head1; } if (head1->data <= head2->data) { head1->next = merge_recursive(head1->next, head2); return head1; } else { head2->next = merge_recursive(head1, head2->next); return head2; } } ``` 在这个递归过程中，我们每次选择较小的头节点作为新链表的头，然后递归地处理剩下的部分，直到其中一个链表为空。 ### 单链表逆序 逆序单链表的操作涉及改变每个节点的`next`指针，使其指向前一个节点。可以使用迭代或递归方法实现。这里给出一个迭代的实现： ```cpp node* reverse(node* head) { node* prev = NULL; node* current = head; node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } ``` 这个函数通过三个指针`prev`、`current`和`next`来跟踪当前节点及其前后节点，逐个调整`next`指针，最后返回新的头节点。 总结来说，本文探讨了如何在单链表中进行合并和逆序操作，提供了非递归和递归两种合并方法，以及一个迭代的逆序方法。这些操作在数据结构和算法的学习及实践中具有重要意义。