[Leetcode] 328. 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. 

Example 1:Input: head = [1,2,3,4,5] Output: [1,3,5,2,4]

Example 2:Input: head = [2,1,3,5,6,4,7] Output: [2,3,6,7,1,5,4]  

Constraints:The number of nodes in the linked list is in the range [0, 104].-106 <= Node.val <= 106

 

풀이

 

먼저 첫 노드를 표시할 3개의 포인터를 만든다. odd-indexed node를 위한 포인터, even-indexed node를 위한 포인터, 그리고 나중에 두 리스트를 이어줄 (even list의 head를 포인트하는) 포인터.

 

while 은 마지막 even 노드나 odd 노드(even->next) 가 없을때 까지 진행된다.

각각의 리스트를 업데이트하고 next노드로 넘어가면 된다.

 

마지막에 두 odd, even lists 를 이어주고 return한다.

 

코드

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* oddEvenList(struct ListNode* head) {
    if(!head) return head;
    
    struct ListNode* odd = head;
    struct ListNode* even = head->next;
    struct ListNode* evenHead = head->next;

    while(even && even->next) {
        odd->next = even->next;
        even->next = odd->next->next;
        odd = odd->next;
        even = even->next;
    }
    odd->next = evenHead;
    return head;
}