脚本宝典收集整理的这篇文章主要介绍了

143. Reorder List

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

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;
        }
    }
}

总结

以上是脚本宝典为你收集整理的

143. Reorder List

全部内容,希望文章能够帮你解决

143. Reorder List

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过