C语言笔试题之重排链表

重排链表

实例要求

1、给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

2、请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

3、不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；
示例：

实例分析

1、找到链表的中间节点，可以使用快慢指针法。
2、将链表分为两部分，前半部分和后半部分。
3、将后半部分反转。
4、将两个部分交替合并。

示例代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
void reorderList(struct ListNode* head) {if (head == NULL || head->next == NULL || head->next->next == NULL) return;// 快慢指针找中间节点struct ListNode *slow = head;struct ListNode *fast = head;while (fast->next != NULL && fast->next->next != NULL) {slow = slow->next;fast = fast->next->next;}// 将链表分为两部分struct ListNode *secondHalf = slow->next;slow->next = NULL;// 反转后半部分链表struct ListNode *prev = NULL;struct ListNode *curr = secondHalf;struct ListNode *nextNode;while (curr != NULL) {nextNode = curr->next;curr->next = prev;prev = curr;curr = nextNode;}secondHalf = prev;// 合并两个部分struct ListNode *firstHalf = head;while (secondHalf != NULL) {struct ListNode *nextFirst = firstHalf->next;struct ListNode *nextSecond = secondHalf->next;firstHalf->next = secondHalf;secondHalf->next = nextFirst;firstHalf = nextFirst;secondHalf = nextSecond;}
}