目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:
143. 重排链表
描述:
给定一个单链表 L
的头节点 head
,单链表 L
表示为:
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4] 输出:[1,4,2,3]
示例 2:
输入:head = [1,2,3,4,5] 输出:[1,5,2,4,3]
提示:
- 链表的长度范围为
[1, 5 * 104]
1 <= node.val <= 1000
解题思路:
/**
* 143. 重排链表
* 解题思路:
* 链表长度5*10^4,所以递归的方式不可取。
* 这题如果使用额外的数据结构,比如把链接转换成数组,那么问题就会变得很简单,所以暂且把目标设置为不使用额外空间。
* 使用快慢指针的策略,快指针走两个节点,慢指针走一个节点,这样,我们可以找到中间节点。
* 然后使用头插法,把中间节点后面的所有节点翻转,生成翻转链表foot
* 重新遍历head链表,直到遍历到middle节点。每次遍历,head和foot链表各取一个
*
*/
代码:
class Solution143
{
public:void reorderList(ListNode *head){ListNode *quick = head;ListNode *slow = head;while (true){quick = quick->next;if (quick == nullptr){break;}slow = slow->next;quick = quick->next;if (quick == nullptr){break;}}// 第二块逻辑ListNode *middle = slow;ListNode *foot = nullptr;ListNode *current = middle;while (current != nullptr){ListNode *local = current;current = current->next;local->next = foot;foot = local;}// 第三块逻辑ListNode *header = head->next;ListNode *footer = foot;current = head;while (current != middle){current->next = footer; // 1->5footer = footer->next; // footer=>4current = current->next; // current=>5if (current == middle){break;}current->next = header; // 5->2header = header->next; // header=>3current = current->next; // current=>2}cout << head->val << endl;}
};