[LeetCode] 143. Reorder List - 노드(Node) + 구현(Implementation) JAVA

https://leetcode.com/problems/reorder-list/description/

코드설명

노드(Node) + 구현(Implementation) 을 활용합니다.

 

이 문제의 예시와 함께 살펴보겠습니다.

1 2 3 4 5 의 예시입니다.

 

먼저 저의 방식은, 

1. Size = 5 를 구한다.

2. Stack에 1과 2 를 (5 / 2 ) 만큼 이동하며 각각 순서대로 넣습니다. ( 이후에 후입 선출로 사용됩니다. )

3. size가 홀수이므로 가운데 위치 toNextPointer 에 3 을 참조시킵니다. (이때 Cycle을 삭제시키기 위해 toNextPointer의 next = null 로 수정해주어야 합니다. )

4. Stack에서 2를 POP. right에는 현재 head 값을 참조시키면 4가 됩니다.

5. 4 -> toNextPointer를 가리키도록 합니다. 2 -> 4 를 가리키도록 합니다. 그러면 2 -> 4 -> 3 이 완성됩니다.

6. toNextPointer가 2를 가리키도록 합니다.

...

...

위의 연결로직인 4번, 5번, 6번을 반복합니다.

 

문제에서 유의할점은,

메모리 객체는 힙에 존재하고,

우리가 만든 ListNode 포인터들은 스택(지역변수)로써 존재한다는 점 입니다.

그러므로, 우리의 포인터(참조)값들에 힙 객체의 값을 대입한다고 해도, 해당 힙에 존재하는 객체들이 변화하는것이 아닙니다.

코드

정답코드1입니다.

/**
 * 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 void reorderList(ListNode head) {
        int size = 0;
        ListNode dummy = new ListNode(-999);
        dummy.next = head;
 
        Stack<ListNode> leftStack = new Stack<>();
        while(head != null){
            head = head.next;
            size += 1;
        }
        ListNode toNextPointer = null;
 
        int tempSize = 0;
        head = dummy.next;
        
        while(tempSize++ < size / 2){
            leftStack.push(head);
            head = head.next;   
        }
 
        
        if(size % 2 == 1){
            toNextPointer = head;
            head = head.next;
            toNextPointer.next = null;
        }
 
        while(head != null && !leftStack.isEmpty()){
            ListNode right = head;
            ListNode toNextHeadStore = head.next;
            ListNode left = leftStack.pop();
            right.next = toNextPointer;
            left.next = right;
            toNextPointer = left;
            head = toNextHeadStore;
        }
        return ;        
    }
 
 
}