143. Reorder List

문제

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.

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

Solution 1

class Solution {
  public void reorderList(ListNode head) {
    if (head == null || head.next == null)
      return;

    ListNode mid = findMid(head);
    ListNode reversed = reverse(mid);
    merge(head, reversed);
  }

  private ListNode findMid(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    ListNode prev = null;

    while(fast!=null && fast.next!=null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    prev.next = null;
    return slow;
  }


  private ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;

    while(cur!=null) {
        ListNode next = cur.next;

        cur.next= prev;
        prev = cur;
        cur = next;
        // prev = cur;
    }
    return prev;
  }

  private void merge(ListNode l1, ListNode l2) {
    while(l2!=null) {
        ListNode next = l1.next;

        l1.next = l2;

        l1 = l2;
        l2 = next;
    }


  }




}

• 링크드 리스트의 중간 노드를 찾기 위해 러너(Runner) 기법을 이용하였다.
• 중간 노드를 기점으로 리스트를 분리하고, 뒤의 리스트의 연결을 역순으로 배치한다. 하나의 리스트에서 두 개의 리스트로 분리하므로, 앞의 리스트의 tail은 next를 null로 지정하였다.
• 각 리스트의 head를 기점으로 문제에서 원하는 방식으로 노드 연결을 진행한다.

러너(Runner) 기법

• 연결리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법
• 한 포인터가 다른 포인어보다 앞서게 하여 병합 지점이나 중간 위치, 길이 등을 판별할 때 유용하게 사용할 수 있다.
• 빠른 러너(Fast Runner)는 두 칸씩 건너뛰고 느린 러너(Slow Runner)는 한 칸씩 이동하게 한다.
• 이때 빠른 러너가 연결 리스트의 끝에 도달하면, 느린 러너는 정확히 연결 리스트의 중간 지점을 가리키게 된다.

Solution 2

class Solution {
    public void reorderList(ListNode head) {
        Deque<ListNode> dq = new ArrayDeque<>();
        ListNode start= head;

        while(start!=null) {
            dq.add(start);
            start = start.next;
        }

        ListNode cur = head;
        dq.pollFirst();
        ListNode next = head;
        boolean flag = true;
        while(!dq.isEmpty()){
            if(flag){
                next = dq.pollLast();




            } 
            else {
                next = dq.pollFirst();

            }

            cur.next=next;
            cur=next;
            flag=!flag;
        }

        cur.next =null;
    }
}

Deque에 노드를 순차적으로 삽입(왼쪽 끝)하고 앞, 뒤로 추출하면서 노드를 연결하였다. 앞의 풀이보다 직관적이라고 생각하지만, 큐를 사용하기 때문에 공간 복잡도 비용이 든다.

회고

풀이 1 덕분에 링크드 리스트의 중간 노드를 찾는 기법(러너 기법)을 배웠다. 또한, 두 리스트의 head를 기준으로 순차적으로 노드를 연결하는 로직이 필요했는데, 다른 풀이에서는 연결 과정이 직관적으로 이해되지 않았지만, 위의 풀이에서는 그 과정이 명확하게 이해되었다. 빨간색 박스는 while문 내에서 실행될 코드를 나타내며, 이 안에서 노드 간의 관계가 정의되어 있다.

  private void merge(ListNode l1, ListNode l2) {
    while(l2!=null) {
        ListNode next = l1.next;

        l1.next = l2;

        l1 = l2;
        l2 = next;
    }