C语言PTA链表-查找链表最后节点

### C语言 PTA 2-5 题重排链表解决方案 为了实现给定单链表的重新排列，可以采用双指针法来完成这一操作。具体来说，在遍历过程中将原链表分为两部分，并反转第二部分，最后交替连接这两部分节点。 #### 定义结构体与辅助函数 定义一个简单的链表节点结构体以及一些必要的辅助函数用于创建新节点、打印链表等： ```c #include <stdio.h> #include <stdlib.h> typedef struct ListNode { int val; struct ListNode *next; } ListNode; // 创建新的列表节点 ListNode* createNode(int value) { ListNode *new_node = (ListNode *)malloc(sizeof(ListNode)); new_node->val = value; new_node->next = NULL; return new_node; } // 打印整个列表的内容 void printList(ListNode *head) { while(head != NULL){ printf("%d", head->val); if(head->next!=NULL) printf(" -> "); head = head->next; } printf("\n"); } ``` #### 主要逻辑处理过程 接下来是核心算法部分，这里会先找到中间位置并断开前后半段，再翻转后半段链表，最终按照题目要求的方式拼接起来[^1]。 ```c // 反转链表 ListNode* reverseList(ListNode *head) { ListNode *prev = NULL, *curr = head, *next; while(curr){ next = curr->next; // 记录下一个节点 curr->next = prev; // 当前节点指向前一个节点 prev = curr; // 更新前驱为当前节点 curr = next; // 移动到下一位继续循环 } return prev; } // 寻找链表中点并将之后的部分截取出来作为另一条链表返回 ListNode* splitAndReverseSecondHalf(ListNode **headRef) { ListNode *slowPtr = *headRef, *fastPtr = (*headRef)->next; while(fastPtr && fastPtr->next){ // 使用快慢指针定位至中心处 slowPtr = slowPtr->next; fastPtr = fastPtr->next->next; } ListNode *second_half_start = slowPtr->next; // 获取右半边起始点 slowPtr->next = NULL; // 断开左半边 return reverseList(second_half_start); // 返回已逆序后的右边链表头 } // 合并两个交错链接的链表 void mergeAlternately(ListNode **leftHead, ListNode *rightReversedTail) { ListNode *currentLeft = *leftHead; ListNode *tempNextRight; while(currentLeft && rightReversedTail){ tempNextRight = rightReversedTail->next; // 存储右侧剩余未处理过的节点 rightReversedTail->next = currentLeft->next;// 将右侧节点插入左侧对应位置之前 currentLeft->next = rightReversedTail; // 插入完成后更新左侧指向 currentLeft = currentLeft->next->next; // 跳过刚插入的那个元素移动到下一组待处理的位置 rightReversedTail = tempNextRight; // 继续处理剩下的右侧节点 } } ``` #### 测试案例构建与调用上述功能组合解决问题 现在有了这些工具函数的支持，就可以轻松解决这个问题了。下面是一个完整的例子展示如何读取输入数据建立初始链表，执行重组动作后再输出结果[^2]。 ```c int main() { // 假设已经获取到了首地址和长度信息... int n = 6; // 示例中的数量 char firstAddrStr[] = "0"; // 示例第一个结点地址字符串形式 long addrFirst = atol(firstAddrStr); // 构建测试用例链表 {1,2,3,4,5,6} ListNode *test_head = createNode(1), *p=test_head; for(int i=2;i<=n;++i){ p->next=createNode(i); p=p->next; } // 开始处理：分割+反转+合并 ListNode *reversed_second_part = splitAndReverseSecondHalf(&test_head); mergeAlternately(&test_head, reversed_second_part); // 输出调整后的链表序列 printList(test_head); return 0; } ``` 此代码片段展示了如何利用C语言在PTA平台上解答“7-2 重排链表”这道编程题目的方法。通过合理的模块化设计使得整体思路清晰易懂，同时也提高了代码可维护性和扩展性[^3]。

### C语言链表节点最大值解决方案 在处理单链表中的节点最大值问题时，通常会遍历整个链表来找到最大的数值。下面是一个完整的实现方法： #### 函数定义 为了获取单链表 `List` 中的最大值，可以编写如下接口函数： ```c int MaxValue(List L); ``` 此函数接收一个指向链表头结点的指针作为参数，并返回该链表中所有节点存储整数的最大值。 #### 数据结构定义 假设使用的链表节点结构体定义如下所示[^2]: ```c typedef struct Node { int data; struct Node *next; } ListNode, *List; ``` #### 实现逻辑 通过迭代方式访问每一个节点并比较其数据域的内容，从而找出最大值。具体代码实例如下: ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点结构 typedef struct Node { int data; struct Node *next; } ListNode, *List; /** * 获取链表中节点的最大值 */ int MaxValue(List L) { if (L == NULL || L->next == NULL) return 0; // 如果列表为空，则返回0 List current = L->next; // 初始化current为第一个实际元素的位置 int maxVal = current->data; // 假设当前的第一个有效元素即为最大值 while(current != NULL){ if(maxVal < current->data){ maxVal = current->data; } current = current->next; } return maxVal; } ``` 这段代码首先检查传入的链表是否为空；如果不为空则继续执行后续操作。接着初始化变量 `maxVal` 来保存目前发现的最大值，并设置循环条件直到到达链表末端为止，在每次迭代过程中更新 `maxVal` 的值以便最终能够得到全局最大值。