OddEvenLinkedList [source code]

public class OddEvenLinkedList {
static
/******************************************************************************/
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null) {
            ListNode slowParent = slow;
            slow = slow.next;
            if ((fast = fast.next) == null)
                break;
            ListNode fastParent = fast;
            if ((fast = fast.next) == null)
                break;
            /* Two lessons:
                1. always a good habbit to cache next_pointer in linked list manipulation.
                2. try thinking conceptually about what you did if you are stuck trying 
                to see patterns simply from trace. */
            ListNode nextSlow = fast, nextFast = fastParent;
            fastParent.next = fast.next;
            fast.next = slow;
            slowParent.next = fast;
            /* Advance */
            slow = nextSlow;
            fast = nextFast;
        }
        return head;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        OddEvenLinkedList.Solution tester = new OddEvenLinkedList.Solution();
        int[][] inputs = {
            {1,2,3,4,5}, {1,3,5,2,4},
            {1,2,3,4}, {1,3,2,4},
            {1,2,3,4,5,6,7,8}, {1,3,5,7,2,4,6,8},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            ListNode head = ListNode.buildListNode (inputs[2 * i]);
            String inputStr = head.toString ();
            System.out.println (Printer.separator ());
            String ansStr = ListNode.buildListNode (inputs[2 * i + 1]).toString ();
            ListNode output = tester.oddEvenList (head);
            String outputStr = output.toString ();
            System.out.printf ("%s -> %s, expected: %s\n",
                inputStr, Printer.wrapColor (outputStr, outputStr.equals (ansStr) ? "green" : "red"), ansStr
            );
        }
    }
}

大概是有思路的, 不过感觉写起来很麻烦;

这个题目就算是面试不给用自己的代码库的时候, 也要记得自己写一个print linked list的utility, 不然简直是无法debug; 事实上, 任何的LinkedList的题目, 好像都有必要写这个print功能; 别不好意思, debug能力不是也是一种很重要的能力吗. 当然如果是纸面编程, 那就很姜了;

最后是好不容易AC了; 这个题目虽然思路很明确, 但是实际上写起来完全不是那么trivial, 尤其是我用comment标记出来的部分, 好半天才想起来这样处理;

反正得到的教训是, LinkedList的题目, 一定要有明确的advance的概念在脑子里; 而且为了让你的advance更加省心, 记得要提前cache. 比如这题, 因为这个cache, 之后的advance才更加简单; 如果没有这个过程, 简直是要命;

另外, 注意看我这里在increment的时候, 都有注意去记录parent, 这个也是一个可以锻炼的技巧;

算法的核心思路就是把fast的位置先delete掉, 然后insert到slow的前面就行了; 变量更新是一个难点;

最后的速度是1ms (3%), 估计也是波动内的最优解了;

editorial给的解法不是InPlace的:

The best way of solving any linked list problem is to visualize it either in your mind or on a piece of paper.

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

不对, 这个是InPlace的, https://leetcode.com/problems/odd-even-linked-list/solution/

最后整个算法还是很简练的; 看一下他的图画:

可以看到, 他这个其实是在计算的过程中还是split成两段了, 这也是为什么他要专门有一个evenHead, 因为用来记录另外一个list; 然后最后简单的append一下就行了: 这个没有cost, 因为你最后是有一个pointer at end的;

整体来说我感觉这个算法比我的想法要简单很多; 如果我一开始想到从非InPlace的做法开始优化(从笨办法优化), 那么可能我能想到这个思路;

discussion基本都是上面类似的一个算法;

submission也都是那个一样的算法;

Problem Description

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

Given 1->2->3->4->5->NULL,  
return 1->3->5->2->4->NULL.

Note:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on ...

Credits:

• Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:83.7K
Total Submissions:188.7K
Contributor:LeetCode
Related Topics
linked list
Similar Questions
Split Linked List in Parts