May LeetCoding Challenge[Day16] - Odd Even Linked List

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.

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 ...
The length of the linked list is between [0, 10^4].

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 해당 문제는 LinkedList가 주어졌을 때, 0246인 짝수 인덱스와 1357인덱스를 나누어서 짝수 인덱스 뒤에 홀수 인덱스의 링크드 리스트를 연결시키는 문제이다.

 - 해당 문제는 O(1) 공간복잡도와 O(nodes)의 시간복잡도가 요구 된다.

 - 첫 번째 노드는 홀수, 두 번째 노드는 짝수로 간주되어진다.

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

- 링크드리스트를 짝수와 홀수를 어떻게 분리시켜서 연결시킬까?

- 링크드리스트의 문제를 풀고 나면 next를 어떻게 시키느냐에 따라서 속도가 달라진다거나, 홀수와 짝수로 분리되는 것을 볼 수 있다. 이러한 점을 이용해서 다음 문제에서는 next를 항상 고민해서 생각해보자.

 

3. 내가 작성한 알고리즘

 

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        
        ListNode oddNode = head;
        ListNode evenNode = head.next; 
        ListNode tempNode = evenNode;
        while(evenNode != null && evenNode.next != null){
            oddNode.next = evenNode.next;
            oddNode = oddNode.next;
            
            evenNode.next = oddNode.next;
            evenNode = evenNode.next;
        }
        oddNode.next = tempNode;
        return head;
    }
}

 

4. 결과

 

문제 : https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3331/

Account Login - LeetCode