###### tags: `Leetcode` `medium` `list` `python` `c++`

# 328. Odd Even Linked List

## [題目連結:] https://leetcode.com/problems/odd-even-linked-list/

## 題目:
Given the ```head``` of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The **first** node is considered **odd**, and the **second** node is **even**, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in ```O(1)``` extra space complexity and ```O(n)``` time complexity.


## 解題想法:
* 此題為，將list中奇數的node移到前面，偶數的node移到後面

* 想法:
* **把所有奇數位置的node連到一起、偶數位置的node連到一起**
* **最後將奇數的最後一個node指向偶數list的head**
* 變數:
* dummy: 紀錄最後結果
* **odd**=head :紀錄奇數node
* **even**=head.next: 紀錄偶數node
* tail=even :紀錄偶數list的head
* while判斷 even and even.next:
* Step1: odd.next=even.next
* Step2: odd=odd.next
* Step3: even.next=odd.next
* Step4: even=even.next
* 最後將odd.next=tail
* return dummy.next
* 示意圖:

## Python:

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        head=self
        stack=[]
        while head:
            stack.append(head.val)
            head=head.next
        print(stack)

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head :
            return head
        dummy=ListNode(0)
        dummy.next=head
        odd=head
        even=head.next
        tail=even
        while even and even.next:
            odd.next=even.next
            odd=odd.next
            even.next=odd.next
            even=even.next
        odd.next=tail
        return dummy.next
        
head=ListNode(1)
head.insert(2)
head.insert(3)
head.insert(4)
head.insert(5)
print("Original:",end='')
head.printList()

result = Solution()
ans = result.oddEvenList(head)
print("After:",end='')
ans.printList()

## C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head)
            return nullptr;
        ListNode *dummy=new ListNode(0);
        dummy->next=head;
        ListNode *odd=head, *even=head->next;
        ListNode *tail=even;
        while (even && even->next){
            odd->next=even->next;
            odd=odd->next;
            even->next=odd->next;
            even=even->next;
        }
        odd->next=tail;
        return dummy->next;
    }
};