美文网首页
链表奇偶数排序(Leetcode328)

链表奇偶数排序(Leetcode328)

作者: zhouwaiqiang | 来源:发表于2018-11-13 14:30 被阅读0次

    题目

    • 给定一个链表,将其奇数排序在前,偶数排序在后(相对位置的顺序值,不是节点值)
    • 举例1->2->3->4->5排序后为1->3->5->2->4,2->1->3->5->6->4->7->NULL排序后为2->3->6->7->1->5->4->NULL

    解题方法

    • 有点类似于leetcode86,可以设置一个奇数链表和偶数链表,对原始链表进行遍历,然后奇数节点放入奇数链表,偶数节点放入偶数链表,最后奇数最后一个节点next指向偶数链表的头节点,返回奇数头节点即可。

    代码实现1

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode oddEvenList(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode odd = head, even = head.next;
            ListNode oddLast = odd, evenLast = even;//奇偶数链表最后一个节点
            head = head.next.next;
            int count = 0;
            while (head != null) {
                count++;
                ListNode temp = head;
                head = head.next;
                if (count % 2 == 0) {
                    temp.next = evenLast.next;
                    evenLast.next = temp;
                    evenLast = evenLast.next;
                } else {
                    temp.next = oddLast.next;
                    oddLast.next = temp;
                    oddLast = oddLast.next;
                }
            }
            oddLast.next = even;
            evenLast.next = null;
            return odd;
        }
    }
    
    • 这个实现的时间消耗比较低,leetcode通过所需时间3ms

    代码实现2(和以上类似)

    private ListNode oddEvenListBackup(ListNode head) {
            ListNode odd = new ListNode(0);
            ListNode even = new ListNode(0);
            ListNode oddIndex = odd, evenIndex = even;
            ListNode temp = head;//暂存节点索引
            int count = 0;
            while (head != null) {
                count++;
                temp = head;
                head = head.next;
                if (count % 2 == 0) {
                    //偶数
                    temp.next = evenIndex.next;
                    evenIndex.next = temp;
                    evenIndex = evenIndex.next;
                } else {
                    //奇数
                    temp.next = oddIndex.next;
                    oddIndex.next = temp;
                    oddIndex = oddIndex.next;
                }
            }
            oddIndex.next = even.next;//奇数下一个置为偶数
            return odd.next;
        }
    
    • 消耗时间6ms较高,因为增加了头结点开销

    相关文章

      网友评论

          本文标题:链表奇偶数排序(Leetcode328)

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