❓143. 重排链表
难度:中等
给定一个单链表 L
的头节点 head
,单链表 L
表示为:
L 0 L_0 L0 → L 1 L_1 L1 → … → L n − 1 L_{n-1} Ln−1 → L n L_n Ln
请将其重新排列后变为:
L 0 L_0 L0 → L n L_n Ln → L 1 L_1 L1 → L n − 1 L_{n-1} Ln−1 → L 2 L_2 L2 → L n − 2 L_{n-2} 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 ∗ 1 0 4 ] [1, 5 * 10^4] [1,5∗104]
- 1 < = n o d e . v a l < = 1000 1 <= node.val <= 1000 1<=node.val<=1000
💡思路:寻找链表中点 + 链表逆序 + 合并链表
- 使用 快慢指针 寻找链表中点,将链表分割成两个链表;
- 然后把第二个链表利用 头插法 反转;
- 之后在通过两个链表拼接成新的链表,将第二个链表插到第一个链表。
🍁代码:(Java、C++)
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){//找到中间节点
slow = slow.next;
fast = fast.next.next;
}
fast = slow.next;//后半部分的第一个
if(fast == null) return;
slow.next = null;//截断为两部分
//将后半部分头插法进行重排序
ListNode h = fast;
fast = h.next;
h.next = null;
while(fast != null){
slow = fast;
fast = fast.next;
slow.next = h;
h = slow;
}
//前后两部分合并
slow = head;//指向前半部分
fast = h;//指向后半部分
while(fast != null){//将后半部分插入到前半部分
fast = fast.next;
h.next = slow.next;
slow.next = h;
slow = h.next;
h = fast;
}
}
}
C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head->next;
while(fast != nullptr && fast->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
fast = slow->next;//后半部分的第一个
if(fast == nullptr) return;
slow->next = nullptr;//截断为两部分
//将后半部分头插法进行重排序
ListNode* h = fast;
fast = h->next;
h->next = nullptr;
while(fast != nullptr){
slow = fast;
fast = fast->next;
slow->next = h;
h = slow;
}
//前后两部分合并
slow = head;
fast = h;
while(fast != nullptr){
fast = fast->next;
h->next = slow->next;
slow->next = h;
slow = h->next;
h = fast;
}
}
};
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
O
(
n
)
O(n)
O(n),其中
n
是链表中的节点数。 - 空间复杂度: O ( 1 ) O(1) O(1)。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-481048.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-481048.html
注: 如有不足,欢迎指正!
到了这里,关于(链表) 143. 重排链表 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!