[ leetcode ] Odd Even Linked List

[ 문제링크 ]

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

 

 

[ 문제 이름 ]

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.

 

 

[ 문제 제약 ]

• The number of nodes in the linked list is in the range [0, 10^4].
• -10^5  < = Node.val  < = 10^6

 

 

 

 

 

---

 

[ 리스트노드 구현 클래스 코드 ]

public static class Node {
    int data;
    Node next = null;

    Node(int d) {
        this.data = d;
    }

    void append(int d) {  // 리스트노드 연결하는 메서드
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }

    void retrieve() {  // 리스트노드 검색하는 메서드
        Node n = this;
        while (n.next != null) {
            System.out.print(n.data + " -> ");
            n = n.next;
        }
        System.out.println(n.data);
    }
}

 

 

[ 리스트노드 정렬하는 코드 구현한 함수(우리가 원하는 출력값을 수행하는 찐 코드) ]

public static ListNode oddEvenList(ListNode head) { 
    // ex) 받는 값 : 1 -> 2 -> 3 -> 4 -> 5
    //     출력 값 : 1 -> 3 -> 5 -> 2 -> 4
    //  ( 순서가 홀수인 값들이 먼저 앞으로 정렬되고 그 다음으로 순서가 짝수인 값들이 정렬되는 리스트 출력하기 )

    if (head == null) {
        return null;
    }
    // ListNode odd : 홀수 리스트노드의 next 를 바꿔주기 위한 포인터
    // ListNode even : 짝수 리스트노드의 next 를 바꿔주기 위한 포인터
    // head : 값 1을 가진 리스트노드
    // even : 값 2를 가진 리스트노드
    ListNode odd = head;  // 맨 처음 값을 head 라고 한다. 맨처음으로 들어오는 값 1은 순서가 1번으로 홀수 번수이다.
    ListNode even = head.next; // head 노드에 가지고 있는 next 라는 공간(노드가 가지고 있는 필드)에 그 다음값인 2가 들어있다.
    ListNode evenHead = even;

    while (even != null && even.next != null) {

        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }

    // head(odd) = 1, 3, 5
    // evenHead = 2, 4
    odd.next = evenHead; // 짝수 순번들이 연결되어있는 리스트의 첫번째 값을 홀수 순번들이 연결되어있는 리스트의 마지막
    return head;
}

 

 

 

[ 리스트노드 출력하는 코드 ]

public class EX1_ListNode {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.append(2);
        head.append(3);
        head.append(4);
        head.append(5);

        Node odd = head;
        Node even = head.next;
        Node evenHead = even;

        System.out.println(even);
        System.out.println(evenHead);

        while (even != null && even.next != null) {
            odd.retrieve(); // 12345
            odd.next = even.next; // 345
            odd.retrieve(); // 1345
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }

        odd.next = evenHead;
        head.retrieve();
    }
}

 

 

[ while문 실행되기 전 노드 현황 상태 ]

 

/* 처음 초기 상태 */

   head = one,

   odd = one,

   (odd.next = two)

   even = two,

   (even.next = three)

   evenHead = two

 

 

 

---

[ 처음 while문 odd.next = even.next; 코드 실행 결과 ]

 

 

/* 첫 odd.next = even.next 실행 후 상태 */

   head = one,

   odd = one,

   (odd.next = two  -->  three)

   even = two,

   (even.next = three)

   evenHead = two

 

 

 

 

---

[ 처음 while문 odd = odd.next; 코드 실행 ]

 

[ odd = odd.next; 코드 실행 결과 ( odd 가 노드 3을 가리키게 되고 odd.next는 노드 4를 가리키게 된다. ) ]

 

 

/* 첫 odd = odd.next 실행 후 상태 */

   head = one,

   odd = one  -->  three,

   (odd.next = three  -->  four)

   even = two,

   (even.next = three)

   evenHead = two

 

 

 

---

 

[ 처음 while문 even.next = odd.next; 코드 실행한 경우 ]

 

 

 

[ even.next = odd.next 코드 실행한 후 바뀌는 부분 ( even.next 가 노드 4를 가리키게 된다. ) ]

 

 

 

/* 첫 even.next = odd.next 실행 후 상태 */

   head = one,

   odd = three,

   (odd.next = four)

   even = two,

   (even.next = three  -->  four)

   evenHead = two

 

 

 

---

 

[ 처음 while문 even = even.next; 코드 실행한 경우 ]

 

 

[ even = even.next 코드 실행한 후 결과 (even이 노드 4를 가리키게 되므로 even.next는 노드 5를 가리키게 된다.) ]

 

 

 

/* 첫 even = even.next 실행 후 상태 */

   head = one,

   odd = three,

   (odd.next = four)

   even = two  -->  four,

   (even.next = four  -->  five)

   evenHead = two

 

 

 

여기까지 while문 한번 다 돌게 된 상태!

이때, whlie문의 조건 even != null && even.next != null 이 true인 상황이므로

다시한번 더 while문 반복문을 돌게 된다.

 

 

 

[ 두번째 whle문 실행시, odd.next = even.next; 코드 실행한 경우 (odd.next가 원래 노드 4를 가리켰는데 노드 5를 가리키는 even.next로 바뀐다.) ]

 

 

[ odd.next = even.next 코드 실행 후 결과 ]

 

 

/* 두번째 odd.next= even.next 실행 후 상태 */

   head = one,

   odd = three,

   (odd.next = four  -->  five)

   even = four,

   (even.next = five)

   evenHead = two

 

---

 

[ 두번째 while문 실행 시, odd = odd.next 코드 실행한 경우 ]

 

 

[ odd = odd.next 코드 실행 한 후의 결과 ]

 

 

/* 두번째 odd= odd.next 실행 후 상태 */

   head = one,

   odd = three --> five,

   (odd.next = five  -->  null)

   even = four,

   (even.next = five)

   evenHead = two

 

---

 

[ 두번째 while문 실행 시, even.next = odd.next 코드 실행한 경우(5가 있던 even.next 자리에 odd.next 인 null값을 넣어줬다.) ]

 

 

 

/* 두번째 even.next = odd.next 실행 후 상태 */

   head = one,

   odd = five,

   (odd.next = null)

   even = four,

   (even.next = five  -->  null)

   evenHead = two

 

 

 

 

---

 

[ 두번째 while문 실행 시, even = even.next 코드 실행한 경우(노드 4를 가리키던 even이 null을 가리키게 된다.) ]

 

 

/* 두번째 even = even.next 실행 후 상태 */

   head = one,

   odd = five,

   (odd.next = null)

   even = four  -->  null,

   (even.next = null)

   evenHead = two

 

 

 

 

여기서 even.next = null이고 even = null 이 되므로

while문의 조건문 even != null && even.next != null 이 false가 되어서

더이상 while문을 돌 수가 없게 된다. 

 

 

 

[ while문에서 빠져 나오면 있는 odd.next = evenHead; 코드 실행한 경우 ]

 

 

 

[ 최종적인 리스트노드 현황 ]