<Medium> Reorder List (LeetCode : C#)

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

📕 문제 설명

단일 연결 리스트의 head가 주어졌을 때 1)을 2)와 같이 순서를 재배치하여 반환

1)

2)

list value를 변경할 수 없으며, 노드 자체만 변경 가능

• Input
  단일 연결리스트의 head
• Output
  순서 재배열 한 후의 리스트 (반환 type 따로 x, 주어진 것 자체의 순서 변경)

예제

풀이

처음 쭉 돌면서 길이랑 stack에 담아두기
그 다음 stack에서 pop하면서 뒤에 위치한 노드 하나씩 가져오고 가져온 노드는 앞 노드의 다음을 가리키게 한다. 그리고 제일 앞에 해당 되는 노드의 다음을 pop한 노드로 가리키면 문제에서 제시한 형태로 순서가 변환된다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) {
        Stack<ListNode> nodeStack = new Stack<ListNode>();
        ListNode tempNode = head;
        int cnt = 0;

        while (tempNode != null)
        {
            cnt++;
            nodeStack.Push(tempNode);
            tempNode = tempNode.next;
        }

        tempNode = head;

        for (int i = 1; i <= cnt / 2; i++)
        {
            ListNode temp = tempNode.next;
            ListNode lastNode = nodeStack.Pop();
            tempNode.next = lastNode;
            lastNode.next = temp;
            tempNode = temp;
        }

        tempNode.next = null;
        
    }
}

결과