【探索-中级算法】奇偶链表

首先，一定要理解题目。

然后就是规定限制条件，要使用原地算法，空间复杂度要为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

1、基于原地算法，但是时间复杂度为 O(n^2)

public ListNode oddEvenList(ListNode head) {
    if (head==null) return head;
    ListNode node = head;
    int len = 0;
    //得到节点数
    while (node != null) {
        ++len;
        node = node.next;
    }
    int t = (len % 2 == 0) ? len : len - 1;
    ListNode tmp = head.next;//保存上一次循环开始的节点
    // (len-1)/2 即为总共处理的次数
    for (int i = (len-1)/2; i >=1; i--) {
        //每次处理的组数（相邻两个为一组）
        ListNode start = tmp;
        for (int j = 0; j < i; j++) {
            int change = start.val;
            start.val = start.next.val;
            start.next.val = change;
            start = start.next.next;
        }
        tmp = tmp.next;
    }
    return head;
}

实现的思想就类似与冒泡排序，即按照一定规律交换当前节点与下一个节点，从而实现题目的要求。

总的循环次数为 (总节点数-1)/2。需要注意的是，总节点数为奇数为偶数时，因为最后一个节点为偶数节点且时最后一位，所以不需要参与操作，因此就有 总节点数-1 再去除以 2。

2、基于原地算法，时间复杂度为 O(n)
参考自：https://blog.csdn.net/NoMasp/article/details/50535947

借助单链表的特性，当前节点的下一个节点总是与当前节点相连的。

正常的思维一般是把两个链表合并在一起，就像把拉链拉来，但是也可以有逆向思维，反着把拉链拉开。

如下图：

public static ListNode oddEvenList2(ListNode head) {
    if (head==null) return head;
    ListNode jiNode = head;
    ListNode ouNode = head.next;
    ListNode firstOuNode = ouNode;//用于记录最开始的偶数节点，用于后面的拼接
    while (jiNode.next != null && ouNode.next != null) {
    	//将该节点的下一个节点更新为原偶数节点的后一位，即奇数节点
        jiNode.next = ouNode.next;
        //将指针移到新的奇数节点
        jiNode = jiNode.next;
        ouNode.next = jiNode.next;
        ouNode = ouNode.next;
    }
    jiNode.next = firstOuNode;
    return head;
}

需要注意的就是 jiNode 和 ouNode 在移动时的先后顺序了。