악역영애의 개발일지

ListNode 에서 홀수 index, 짝수 index를 뽑아서 짝수 index는 순서대로 뒤로 나열하는 문제다.

우선 홀짝을 순서대로 뽑아보자

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
    }
}

이렇게 초기화를 한 상태에서 head.next가 없을때까지 돌려야할것같은데..

우선 홀-짝-홀-짝 이런순서로 가니까 무조건 짝이 뒤에올것이기때문에 while문에 조건을 넣어줬다.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
    }
}

이렇게되면 even에는 .next.next를 넣었으니, even= even.next 를 실행했을때 next값이 null 이라면 while문은 돌지않을것이다.

그런데 

1 -> 2 -> 3 -> 4 -> 5

예시가 있다고 하자.

while 문 돌기전에 odd = 1, even = 2

첫번째 while 문에서

odd = 3, odd.next = 5

even = 4, even.next = null 이다.

두번째 while문에서 odd = 5, even = null 이기때문에 nullpointException 발생한다.

따라서 while문을 수정해주자.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null && even.next != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
    }
}

이렇게하면 비록 두번째 루프는 돌지않았지만, odd.next를 설정했으므로 odd의 세팅이 완료된다.

그리고 최종적으로 기존의 odd 뒤에 even을 붙여준다.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null && even.next != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
        odd.next = even;
        
        return head;
    }
}

그리고 최종적으로 return 은 head를 해준다.

왜냐하면 odd를 return 하면 odd의 시작점을 알수없기때문~

마지막으로 null 예외케이스를 넣어주면

class Solution {
    public ListNode oddEvenList(ListNode head) {
    
    	if (head == null) return null;
        
        ListNode odd = head;
        ListNode even = head.next;
        
        while (even != null && even.next != null) {
            odd = odd.next.next;
            even = even.next.next;
            
            odd = odd.next;
            even = even.next;
        }
        odd.next = even;
        
        return head;
    }
}

딱 보면 홀수/짝수로도 생각할수있겠지만, 다음걸 가져와서 현재랑 swap 해주는 느낌으로 해보자

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode node = head;
    }
}

연산 용 node 를 하나 선언해준다.

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode node = head;
        
        while (node != null && node.next != null) {
            int temp = node.val;
            node.val = node.next.val;
            node.next.val = temp;
            node = node.next.next;
        }
        return head;
    }
}

temp에 현재 node.val 을 넣어두고

현재 node.val = next 값으로 넣어주고

next 값은 temp를 넣어줌!!

그리고 2개의 쌍을 바꿨으니 node 위치를 .next.next로 보내준다.

리턴할때는 head를 리턴하는데, node의 포인트는 이미 node의 끝을 향하고있기때문에 head를 보내준다

여기서 요구하는것은 각자 세로로 더하고 뒤집기.

일단 더해보자.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode node = new ListNode(0);
    }
}

우선 결과물을 보관할 ListNode를 선언한다. [0 -> null]

그리고 여기에 저장하고어쩌고하고 리턴하려고 하면 return node 할때는 node 전체를 보내는게아니라

node의 마지막에 포인터가 가있고, 마지막부분을 return 하기때문에 root를 따로 보관해준다.

만약 ListNode 의순서를 바꾼다거나, 파라미터로 받은 ListNode 를 변경할때에는 해당 ListNode 를 그대로 보내줘도되지만, 이렇게새로운 ListNode를 만들게 될 때는 root를 따로 보관해줘야 한다.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode node = new ListNode(0);
       ListNode root = node;
    }
}

자 이제 l1, l2를 더하게 해보자.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode node = new ListNode(0);
       ListNode root = node;
       
       int sum = 0;
       while (l1 != null || l2 != null) {
          if (l1 != null) {
          	sum += l1.val;
          }
          
          if (l2 != null) {
          	sum += l2.val;
          }
       }
    }
}

우선 이렇게 sum 에 각각의 node를 더해준다.

그리고 10의 자릿수를 넘을수도있으니까 나머지만 node에 저장해두고 넘어가자.

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode node = new ListNode(0);
       ListNode root = node;
       
       int sum = 0;
       while (l1 != null || l2 != null || sum >0) {
          if (l1 != null) {
          	sum += l1.val;
            l1 = l1.next;
          }
          
          if (l2 != null) {
          	sum += l2.val;
            l2 = l2.next;
          }
         
          node.next = new ListNode(sum%10);
          sum /= 10;
          node = node.next;
       }
       return root.next;
    }
}

sum 을 10으로 나눴을때 0이 남으므로 조건도 넣어주고

node.next 에 sum을 10으로 나눈 나머지만 저장한다.

그리고 sum은 10으로 나눈값을 저장해둔다. 그러면 올림처리가 된것처럼 사용할 수 있음.

마지막으로 node의 포인터를 움직여준다.

포인터를 움직여주는 이유는,

최초의 node : 0 -> null

node.next = new ListNode : 0 -> sum%10 -> null

이렇게 최초의 0과 null 사이에 낑기기 때문에, next를 해줘야 sum%10 값에 포인터가 위치하게 된다.

또한 new ListNode를 하는이유도, sum은 단순 int 이기때문에 node에 넣으려면 저렇게 해야한다.

ListNode 를 뒤집을때 일단 첫번째로 생각해야하는것이 있다.

5 4 3 2 1 이 순서로 만들 생각을 하지말고

1 ->null

2 -> 1 -> null

3 -> 2 -> 1 -> null

이순서로 만들 생각을 해야된다.

첫번째 방법 - 재귀

재귀함수를 이용해보는 방법이다.

일단 함수호출하고 현재와 과거의 list를 보낸다고 생각해보자.

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    public ListNode reverse(ListNode node, ListNode prev) {
    }
}

그리고나서 node.next = prev 를 붙일 생각을 해보자.

이때 node.next 는 별도장소에 보관하고있다가 다시 함수를 호출하기를 반복한다.

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }
    
    public ListNode reverse(ListNode node, ListNode prev) {
        if (node == null) return prev;

        ListNode next = node.next;
        node.next = prev;
        return reverse(next, node);
    }
}

계속 돌아서 next가 없고 prev만 있다면 reverse가 완료된것이다.

요점은 next를 별도에 보관하고있다가 node.next 를 prev로 설정한것!

두번째방법 - 반복문

반복문도 비슷하게 흘러간다.

우선 현재 node 와 prev를 담을 변수를 생성해준다

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head, prev = null;
    }
}

그리고 node.next를 별도로 저장하다가

node.next = prev 로 해주고

prev = 현재노드를 해준다.

node = next 노드이기때문에, node를 next 값으로 옮겨준다.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode node = head, prev = null;

        while(node != null) {
            ListNode next = node.next;
            node.next = prev; // node.next = null
            prev = node; // prev = [1, null]
            node = next; // node = [2,3,4]
        }
        return prev;
    }
}

정렬되어있는 상태의 2개의 ListNode  이것을 비교하고 가장 작은 수가 무엇인지 확인 후

return 할 list에 add 해가는게 좋아보인다.

책에서는 재귀함수를 추천했다.

list1 과 list2의 현재값을 비교한다음, 더 작은쪽의 next 값을 재세팅 하는 방식이다.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //두개의 list 값중에 낮은 숫자를 알아내야하고 null인 경우도 고려해야된다.

        if (list1.val < list2.val) {
            list.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

만약 list 1 = [1,2] & list2 = [1,3] 이렇게 있다고 해보자.

1.

else 로 들어가서 list2.next = mergeTwoLists([1->2], 3)

이렇게 보낼것이다..

2.

첫번째 if로 들어가서 list1.next = mergeTwoLists(2, 3)

3. 

첫번째 if로 들어가서 list1.next = mergeTwoLists(null, 3)

이제 list1.next 는 없으니까  위에 걸러주는 것을 만들어주자.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val < list2.val) {
        	//list2가 더 클 경우
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
        	//list1이 더 클 경우
        	list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

4.

if null에 걸려서 list2 return.

5.

3번에서 실행됐던 함수로 돌아옴.

list2의 값인 3 이 return 되고 그것이 list1.next = 3

이때 list1은 2 이기때문에 list.next 로 받은 3을 합치면 return 값은 2->3

6. 2번에서 실행됐던 함수로 돌아옴

list1.next = 2->3

기존 list1와 next를 합치면 1->2->3

7. 1번에서 실행했던 함수로 돌아옴

기존 list2와 next를 합치면 1->-1->2->3

이런식으로 비교했을 때 낮은 숫자쪽에 next를 설정하는 방식으로 풀이했다.