迭代

最初的想法

设定odd和even指针,even指向偶数结点,odd指向奇数结点。
又知,even.next指向的是奇数结点,则把该结点“拆下来”,连接到odd的后面。
最后修改odd和even指针,循环遍历即可。

举例:1->2->3->4->5->NULL
初:odd指向1,even指向2。

  1. 把even的next,即结点3,拆下来
  2. 把结点3插入到odd指针的后面,即1的后面
  3. 更新odd和even指针。

链表:1->3->2->4->5->NULL
修改:odd指向3,even指向4。准备下一次遍历。

class Solution {
    public ListNode oddEvenList(ListNode head) { 
        if(head == null || head.next == null){
            return head;
        }
        ListNode odd = head, even = head.next;
        while(even != null && even.next != null){
            // “拆下来的奇结点”nextNode
            ListNode nextNode = even.next;
            even.next = nextNode.next;
            // 把该奇结点插入odd的后面
            nextNode.next = odd.next;
            odd.next = nextNode;
            // 更新odd和even,准备下一次遍历
            odd = odd.next;
            even = even.next;
        }
        return head;
    }
}

时间复杂度$O(n)$,空间复杂度$O(1)$。

新做法

上面的做法是直接在原链表上操作,虽然时间复杂度为$O(n)$,但做的步骤太多了,在Leecode中仅达到这个效果……(太辣鸡了)

执行用时:1 ms, 在所有 Java 提交中击败了8.34%的用户
内存消耗:39.2 MB, 在所有 Java 提交中击败了89.49%的用户

现在的做法是,直接拆成两条链表,一条连接奇数结点,一条连接偶数结点,最后把两链表相连即可。 

同样,举例:1->2->3->4->5->NULL
初:odd指向1,even指向2。
同时,保存evenHead,它指向even,作为偶链表的头指针。

  1. 修改odd指针,让结点1指向结点3,并让odd指向结点3。
  2. 修改even指向,让结点2指向结点4,并让even指向结点4。
    此时指针的指向:
      odd↘
    head->1->3->4->5->NULL
    evenHead->2↗

上面例子仅为一轮循环,当循环结点后,要把奇结点所在的链表与evenHead相连。
代码如下:

class Solution {
    public ListNode oddEvenList(ListNode head) { 
        if(head == null || head.next == null){
            return head;
        }
        ListNode odd = head, even = head.next;
        ListNode evenHead = even;

        while(even != null && even.next != null){ 
            // odd->奇1->偶1->奇2->偶2
            // 奇1向前遍历,与下一个奇2相连
            // 不必担心偶1会丢失,因为even保存着它
            odd.next = even.next;
            odd = even.next;
            // 让偶1连接偶2,继续遍历
            even.next = odd.next;
            even = odd.next;
        }
        // 最后让奇偶链表相连。
        odd.next = evenHead;
        return head;
    }
}

时间复杂度$O(n)$,空间复杂度$O(1)$。