题目地址
https://leetcode-cn.com/problems/reorder-list/
题目描述
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
思路
- 用栈将链表存起来,再遍历链表,将栈pop的元素查到前面的链表间隙中。
- 快慢指针,找到链表中间位置,再将中间及后面元素反转,再遍历链表,将后面链表插入前面链表的间隙中。
题解
/**
* @Author: vividzcs
* @Date: 2021/3/3 11:07 下午
*/
public class ReorderList {
public static void main(String[] args) {
int[] arr = new int[]{1,2,3,4,5};
ListNode head = ListNode.createListNode(arr);
reorderList(head);
ListNode.print(head);
head = ListNode.createListNode(arr);
reorderListV2(head);
ListNode.print(head);
}
/**
* 执行用时: 2 ms , 在所有 Java 提交中击败了 80.16% 的用户
* 内存消耗: 40.5 MB , 在所有 Java 提交中击败了 98.17% 的用户
*/
private static void reorderListV2(ListNode head) {
if (head == null) {
return;
}
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next;
if (fast != null) {
fast = fast.next;
}
}
ListNode mid = reverse(slow);
ListNode current = head;
while (current != slow) {
ListNode next = current.next;
current.next = mid;
mid = mid.next; // 现保存下个节点,因为下一步会修改mid的next指向
current.next.next = next;
current = next;
}
if (current.next == slow) {
current.next.next = null;
} else {
current.next = null;
}
}
private static ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
/**
* 执行用时: 3 ms , 在所有 Java 提交中击败了 42.70% 的用户
* 内存消耗: 42.1 MB , 在所有 Java 提交中击败了9.52%的用户
*/
private static void reorderList(ListNode head) {
if (head == null) {
return;
}
LinkedList<ListNode> stack = new LinkedList<>();
ListNode current = head;
while (current != null) {
stack.add(current);
current = current.next;
}
current = head;
while (current != stack.peekLast() && current.next != stack.peekLast()) {
ListNode next = current.next;
current.next = stack.removeLast();
current.next.next = next;
current = next;
}
// 分奇数偶数节点个数两种情况
if (current.next == stack.peekLast()) {
current.next.next = null;
} else {
current.next = null;
}
}
}
网友评论