0328. Odd Even Linked List #

题目 #

给定单链表头节点head，将所有索引为奇数的节点和所有索引为偶数的节点分别组合在一起，然后返回重新排序的链表。

第一个节点的索引被认为是奇数，第二个节点的索引被认为是偶数，以此类推。

偶数组和奇数组内部的相对顺序应该与输入时保持一致。

需要在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。

思路 #

代码 #

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode Odd = head, Even = head.next;
        ListNode ptrOdd = Odd, ptrEven = Even;
        while (ptrEven != null && ptrEven.next != null) {
            ptrOdd.next = ptrEven.next;
            ptrOdd = ptrOdd.next;
            ptrEven.next = ptrOdd.next;
            ptrEven = ptrEven.next;
        }
        ptrOdd.next = Even;
        return Odd;
    }
}