328.odd-even-linked-list.md

题目地址

https://leetcode.com/problems/odd-even-linked-list/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 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->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 ...

思路

符合直觉的想法是，先遍历一遍找出奇数的节点。然后再遍历一遍找出偶数节点，最后串起来。

但是有两个问题，如果不修改节点的话，需要借助额外的空间，空间复杂度是N。如果修改的话，会对第二次遍历（遍历偶数节点）造成影响。

因此可以采用一种做法： 遍历一次，每一步同时修改两个节点就好了，这样就可以规避上面两个问题。

关键点解析

• 用虚拟节点来简化操作

• 循环的结束条件设置为 odd && odd.next && even && even.next, 不应该是odd && even, 否则需要记录一下奇数节点的最后一个节点，复杂了操作

代码

• 语言支持：JS，C++

JavaScript Code:

/*
 * @lc app=leetcode id=328 lang=javascript
 *
 * [328] Odd Even Linked List
 *
 * https://leetcode.com/problems/odd-even-linked-list/description/
 *
 * algorithms
 * Medium (48.22%)
 * Total Accepted:    137.6K
 * Total Submissions: 284.2K
 * Testcase Example:  '[1,2,3,4,5]'
 *
 * 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 1:
 * 
 * 
 * Input: 1->2->3->4->5->NULL
 * Output: 1->3->5->2->4->NULL
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: 2->1->3->5->6->4->7->NULL
 * Output: 2->3->6->7->1->5->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 ...
 * 
 * 
 */
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if (!head || !head.next) return head;

    const dummyHead1 = {
        next: head
    }
    const dummyHead2 = {
        next: head.next
    }

    let odd = dummyHead1.next;
    let even = dummyHead2.next;
    
    while(odd && odd.next && even && even.next) {
        const oddNext = odd.next.next;
        const evenNext = even.next.next;
        
        odd.next = oddNext;
        even.next = evenNext;

        odd = oddNext;
        even = evenNext;
    }

    odd.next = dummyHead2.next;

    return dummyHead1.next;

};

C++ Code：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) return head;
        auto odd = head, evenHead = head->next, even = head->next;
        // 因为“每次循环之后依然保持odd在even之前”，循环条件可以只判断even和even->next是否为空，修改odd和even的指向的操作也可以简化
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};