美文网首页
2021-03-03 143. 重排链表

2021-03-03 143. 重排链表

作者: 止戈学习笔记 | 来源:发表于2021-03-03 23:52 被阅读0次

    题目地址

    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.
    

    思路

    1. 用栈将链表存起来,再遍历链表,将栈pop的元素查到前面的链表间隙中。
    2. 快慢指针,找到链表中间位置,再将中间及后面元素反转,再遍历链表,将后面链表插入前面链表的间隙中。

    题解

    /**
     * @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;
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:2021-03-03 143. 重排链表

          本文链接:https://www.haomeiwen.com/subject/vmhhqltx.html