143. Reorder List

淡淡的烟草味﹌ 2022-03-07 10:28 101阅读 0赞

Given a singly linked list L: L0→L1→…→Ln-1→Ln,  
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:
    Given 1->2->3->4, reorder it to 1->4->2->3.
    Example 2:
    Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

难度：medium

题目：给定一单链表 L: L0→L1→…→Ln-1→Ln, 重新排序为: L0→Ln→L1→Ln-1→L2→Ln-2→…

思路：先使用快慢指针一个一次走一步，另一个一次走两步，找出中间点。再使用头插法处理后半段，最后合并两链表。

Runtime: 2 ms, faster than 99.27% of Java online submissions for Reorder List.  
Memory Usage: 40.4 MB, less than 100.00% of Java online submissions for Reorder List.

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public void reorderList(ListNode head) {
            if (null == head) {
                return;
            }
            ListNode oneStepPtr = head, twoStepsPtr = head, midPtr = oneStepPtr;
            while (twoStepsPtr != null) {
                midPtr = oneStepPtr;
                oneStepPtr = oneStepPtr.next;
                twoStepsPtr = (null == twoStepsPtr.next) ? null : twoStepsPtr.next.next;
            }
            midPtr.next = null;
            ListNode dummyHead = new ListNode(0), node = null;
            while (oneStepPtr != null) {
                node = oneStepPtr;
                oneStepPtr = oneStepPtr.next;
                
                node.next = dummyHead.next;
                dummyHead.next = node;
            }
            ListNode ptr = head;
            dummyHead = dummyHead.next;
            while (ptr != null && dummyHead != null) {
                node = ptr;
                ptr = ptr.next;
                ListNode qNode = dummyHead;
                dummyHead = dummyHead.next;
                
                qNode.next = ptr;
                node.next = qNode;
            }
        }
    }