当前位置:   article > 正文

leetcode题解-143. Reorder List_leetcode题解pdf java

leetcode题解pdf java

题目

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

本题的目的是实现链表的重排,将最后一个元素插在第一个元素后面,倒数第二元素插在第二个后面。。。。一次类推,所以很直观的思路就是把链表分为前后两部分(使用fast和slow两个指针),然后将后面的链表进行翻转,这样就可以按顺序将两个链表合并。链表翻转的题目我们已经做过了,合并的也做过了,拆分成两个链表的也做过了。所以屡清思路之后就是将三个题目结合在一起而已。代码如下所示:

    public void reorderList(ListNode head) {
        if(head==null || head.next==null || head.next.next==null)
            return;
        ListNode fast=head, slow=head, second;
        //链表切分成前后两个
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        second = slow.next;
        slow.next = null;
        //将后面那个链表进行翻转
        ListNode pre=null, next;
        while(second != null){
            next = second.next;
            second.next = pre;
            pre = second;
            second =  next;
        }
        //将两个链表合并,把第二个链表的每个元素插在第一个链表的后面即可
        fast = head;
        while(pre!=null){
            next = pre;
            pre = pre.next;
            next.next = fast.next;
            fast.next = next;
            fast = fast.next.next;
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

此外还看到了一种使用Hash表做的方法,但是效率极低而且完全没有使用到链表里面的特性,这里就放出来参考一下==代码如下所示,不推荐:

   public void reorderList1(ListNode head) {

        HashMap<Integer, ListNode> nodeMap = new HashMap<>();
        int len = 0;
        ListNode p = head;

        while (p != null) {
            nodeMap.put(len++, p);
            p = p.next;
        }


        int i = 0;
        int j = len - 1;
        for (; i < j - 1; ++i, --j) {
            ListNode tmp = nodeMap.get(i).next;
            nodeMap.get(i).next = nodeMap.get(j);
            nodeMap.get(j).next = tmp;
            nodeMap.get(j - 1).next = null;

        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/658224
推荐阅读
相关标签
  

闽ICP备14008679号