LeetCode 143.重排链表
题目：给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改背叛点内部的值，而是需要实际的举行节点交换。
思绪：找中点，反转，前后逐一重排
https://i-blog.csdnimg.cn/direct/44db6ffdea224a7d8e237b55d6eb3e2d.png
代码：
class Solution {
public void reorderList(ListNode head) {
ListNode mid = middleNode(head);
ListNode head2 = reverseList(mid);
while (head2.next != null) {
ListNode nxt = head.next;
ListNode nxt2 = head2.next;
head.next = head2;
head2.next = nxt;
head = nxt;
head2 = nxt2;
}
}
private ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
} 性能：
时间复杂度o（n）
空间复杂度o（1）
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]