重排链表
实例要求
- 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;}
}
运行结果