Today I Learned

오늘도 코테코테

206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/description/

문제

Given the head of a singly linked list, reverse the list, and return the reversed list.

Constraints:
The number of nodes in the list is the range [0, 5000].
-5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

풀이과정 & Java 코드

class Solution {
  public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;
    ListNode next = null;
    while (current != null){
      next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    return prev;

  }
}

• 재귀나 반복문으로 구현할 수 있는데, 중요한건 시간복잡도와 공간복잡도이다.

• prev, current, next 3가지 변수를 선언해두고 순회해가면서 앞뒤를 바꾸는 방식으로 문제를 해결했다.

226. Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/description/

문제

Given the root of a binary tree, invert the tree, and return its root.

풀이과정 & Java 코드

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null||(root.left==null && root.right==null)) return root;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

• 위의 문제와 비슷한 결의 문제이다.

• 하지만 이 문제는 추가로 재귀를 사용하여 해결했다.

• 예외처리를 해주고, 재귀로 좌, 우 노드에 들어간뒤 수정해주는 로직을 짜서 해결했다.

• 답안중 가장 빠른 답은 처음으로 받아본 것 같다.