【Leetcode】143. Reorder List

Question：

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Tips：

给定一个单链表，将链表重新排序，注意不能改变结点的值。

排序规则如下：

L₀→L₁→…→L_n-1→L_n,
L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

思路：

重新排序后的链表，前1/2 结点相对顺序不变，而后半部分是逆序。所以我的思路是先将后半部分结点翻转，变为逆序，再将后半部分结点依次插入到前半部分中去。

大致分为三部分:

（1）找到链表的中间位置，将链表分为两部分。

（2）将第二部分链表逆序

（3）将第二部分所有节点依次插入到前半部分结点之间。

代码：

public void reorderList(ListNode head) {

        if (head == null || head.next == null)

            return;

        // Find the part2;第二部分是从slow.next开始的

        ListNode slow = head;

        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

        System.out.println("slow"+slow.val);

        ListNode mid = slow.next;

        slow.next = null;

        System.out.println("mid"+mid.val);

        // 将第二部分翻转;

        ListNode pre = null;

        ListNode cur = mid;

        while (cur != null) {

            if (cur.next != null) {

                ListNode next = cur.next;

                System.out.println("next"+next.val);

                cur.next = pre;

                pre = cur;

                cur = next;

            } else {

                cur.next = pre;

                pre = cur;

                cur=null;

            }

        }

        System.out.println("pre"+pre.val);

        // append one by one;

        ListNode p1 = head;

        ListNode p2 = pre;

        while (p2 != null) {

            ListNode n1 = p1.next;

            ListNode n2 = p2.next;

            p1.next = p2;

            p2.next = n1;

            p1 = p1.next.next;

            p1 = n1;

            p2 = n2;

        }

        //print

        while (head != null) {

            System.out.println(head.val);

            head = head.next;

        }

    }

代码中的一些输出是为了验证结果的正确性提交时可删除。leetcode提交版版代码如下：

public void reorderList(ListNode head) {

        if (head == null || head.next == null)

            return;

        // Find the part2;第二部分是从slow.next开始的

        ListNode slow = head;

        ListNode fast = head;

        while (fast.next != null && fast.next.next != null) {

            slow = slow.next;

            fast = fast.next.next;

        }

        ListNode mid = slow.next;

        slow.next = null;

        // 将第二部分翻转;

        ListNode pre = null;

        ListNode cur = mid;

        while (cur != null) {

            if (cur.next != null) {

                ListNode next = cur.next;

                cur.next = pre;

                pre = cur;

                cur = next;

            } else {

                cur.next = pre;

                pre = cur;

                cur=null;

            }

        }

        // append one by one;

        ListNode p1 = head;

        ListNode p2 = pre;

        while (p2 != null) {

            ListNode n1 = p1.next;

            ListNode n2 = p2.next;

            p1.next = p2;

            p2.next = n1;

            p1 = p1.next.next;

            p1 = n1;

            p2 = n2;

        }

    }

巴特西

【Leetcode】143. Reorder List

最新文章

热门文章