LeetCode-328

题目

结果

代码

新的链表再拼接

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode even = new ListNode(0), odd = new ListNode(0);
        ListNode p1 = even,p2 = odd;

        boolean flag = false;
        ListNode tail = null;

        while (head != null) {
            if (flag) {
                p2.next = new ListNode(head.val);
                p2 = p2.next;
            } else {
                p1.next = new ListNode(head.val);
                p1 = p1.next;
            }

            if (head.next == null) {
                tail = p1;
            }

            flag = !flag;
            head = head.next;
        }
        tail.next = odd.next;
        return even.next;
    }
}

原地算法

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        ListNode oddHead = head, evenHead = head.next;
        ListNode p1 = oddHead, p2 = evenHead;
        ListNode tail = null;
        while (true) {
            if (p2.next == null) {
                tail = p1;
                break;
            }
            if (p2.next.next == null) {
                p1.next = p2.next;
                p2.next = null;
                tail = p1.next;
                break;
            }
            ListNode tmp = p2.next.next;
            p1.next = p2.next;
            p2.next = tmp;
            p1 = p1.next;
            p2 = p2.next;
        }
        tail.next = evenHead;
        return oddHead;
    }
}

复杂度

时间复杂度：O（n）

空间复杂度：第一种O（n），第二种O（1）