6-7주차 연결 리스트(홀짝 연결리스트)

18. 홀짝 연결리스트

https://leetcode.com/problems/odd-even-linked-list/

Odd Even Linked List - LeetCode

📌문제
연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도O(n)에 풀이하라

- 예제1
  📝입력

head = [1,2,3,4,5]

  💻출력

[1,3,5,2,4]

 - 예제2

  📝입력
 

head = [2,1,3,5,6,4,7]

  💻출력
 

[2,3,6,7,1,5,4]

    
📌풀이
0ms, 41.6mb

/**
 * 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 odd = head, even = head.next, evenHead = head.next;
        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            even.next = even.next.next;
            odd = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

- odd: 홀수 even 짝수

- 페어의 노드스왑으로 큰 깨달음을 얻으니까 이 풀이도 쉬워보이더라..

- 소스 그대로 2칸씩 next를 이어가는 방법