6-7주차 연결 리스트(페어의 노드 스왑)

왜 6-7주차냐면 6주차에 푼 문제인데 7주차에 복습을 하기로 해성ㅋ 이 문제 때문에 아이패드를 꺼냈다. 난 집념의 K국가 시민. 깨달음을 얻었다.

 

17. 페어의 노드 스왑

https://leetcode.com/problems/swap-nodes-in-pairs/https://leetcode.com/problems/add-two-numbers/

Add Two Numbers - LeetCode

📌문제
연결 리스트를 입력받아 pair단위로 스왑하라

- 예제1
  📝입력

head = [1,2,3,4]

  💻출력

[2,1,4,3]

 - 예제2

  📝입력
 

head = []

  💻출력
 

[]

    
📌풀이(반복문)

0ms, 39.9mb

public ListNode swapPairs(ListNode head) {
    ListNode prev = new ListNode(0);
    prev.next = head;
    ListNode root = prev;

    while(prev.next!=null && prev.next.next!=null){
        // 1)
        // b가 head를 가키리도록 할당
        ListNode b = head.next;// (2,3,4)
        head.next = b.next; // (1,3,4)
        b.next = head; //(2,1,3,4)
        // 2)
        // prev가 b를 가리키도록 할당
        prev.next = b;
        // 3)
        // 다음 비교를 위해
        head = head.next;
        prev = prev.next.next;
    }
    return root.next;
}

1. 1) 번은 페어끼리 바꿔주는 알고리즘이다.

2. 2) 번에서는 페어가 바뀐 변수가 b에 있으므로 prev.next(0다음부터)로 할당해준다.

3. 3) 번에서는 다음 번 비교를 위해 세팅해준다.

 

내가 이해가 안가던 부분은 이부분이었다. root = prev 인 상태, prev = prev.next.next로 값이 바뀔 텐데 왜 root는 prev랑 값이 다른 것인가.

root는 0->2->1->4->3 이었음

주소값이랑 관련이 있을거라 생각했지만, 확실히 와닿지 못했다. 본능은 알고 있지만, 머리론 이해가 안되는 느낌? 그러다 나는 디버깅을 통해 깨달음을 얻게되는데... 

생각해보면 ListNode는 객체이기 때문에 얕은복사가 된다. 기초적인 걸 난 두 눈으로 직접 확인하고 나서야 깨달았음..

이렇게 prev는 얕은 복사가 되어 주소값만 옮겨간 것. root는 여전이 0을 값으로 가지고 있는 ListNode의 주소를 참조하고 있기 때문에 변경사항만 반영이 되던거더라.

 

소스 설명

📌풀이(재귀구조)

0ms, 40.1mb

public ListNode swapPairs(ListNode head) {
    if ((head == null)||(head.next == null))
        return head;

    // 홀수 인덱스를 가리키기 위함. 홀수와 짝수를 바꿔야 하니까
    // p [2->3->4->null]
    // p [4->null]
    ListNode p = head.next;

    // head.next에 담아주는 이유. 짝수번째 인덱스를 가져오기 위함
    // next.next를 넘겨주는 이유: 페어끼리 비교해야 하니까
    // head [1->4->3->null]
    // head [3->null]
    head.next = swapPairs(head.next.next);

    // 마지막 이어주는 작업
    // 2->1->4->3->null;
    // 4->3->null
    p.next = head;
    return p;
}

- 주석에 적힌 그대로임

 

 

이렇게 분석을 해보니까 연결리스트 문제를 어떻게 접근해야되는 지 감이 온다.