LeetCode 328 奇偶链表

LeetCode 328 奇偶链表

问题描述:
  给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
  请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

执行用时：1 ms, 在所有 Java 提交中击败了7.79%的用户
内存消耗：38.5 MB, 在所有 Java 提交中击败了55.33%的用户

分离出奇、偶节点组建奇、偶链表

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null || head.next==null) {
            return head;
        }
        //双指针一遍扫描: p1指向奇数头节点、p2指向偶数头节点
        ListNode oddHead = head, evenHead = head.next, tmp = evenHead.next;
        oddHead.next = null;
        evenHead.next = null;
        ListNode oddTail = oddHead;
        ListNode evenTail = evenHead;
        int n = 1;
        while(tmp!=null) {
            //奇数节点
            if(n%2==1) {
                oddTail.next = tmp;
                oddTail = oddTail.next;
            }
            //偶数节点
            else {
                evenTail.next = tmp;
                evenTail = evenTail.next;
            }
            tmp = tmp.next;
            oddTail.next = null;
            evenTail.next = null;
            n++;
        }
        oddTail.next = evenHead;
        return oddHead;
    }
}