리트코드 75 15일 차, 링크드 리스트 2문제, 이진트리 순회 1문제를 풀어봤다. 포인터를 활용하는 문제는 언제 풀어도 헷갈리는 면이 있어서 손으로 한번 검증해 보는 게 좋은 것 같다.
328. Odd Even Linked List
Linked list의 head가 주어졌을 때 홀수번째 노드들을 묶고 그 다음에 짝수번째 노드들을 묶은 순서로 바꿔서 리턴하라. 솔루션의 시간 복잡도는 O(n), 공간 복잡도는 O(1) 이 돼야 한다.
Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.
문제를 처음 봤을 때는 좀 막막했는데 노트에 포인터를 직접 옮겨보면서 테스트를 해보니 더 쉽게 풀 수 있었던 것 같다. 홀수번째 노드의 레퍼런스를 저장하는 변수를 odd, 짝수번째 노드의 레퍼런스를 저장하는 변수를 even이라고 하자. 다음 홀수번째 노드의 레퍼런스는 짝수번째 노드의 next에 있고, 다음 짝수번째 노드의 레퍼런스는 다음 홀수 노드의 next에 있기 때문에, 홀수, 짝수 순서로 레퍼런스를 업데이트한다. 첫 번째 노드를 홀수로 보기 때문에 while 문을 나왔을 때 odd가 null인 경우는 없다. (head가 null인 경우는 이미 처리함) 그래서 odd.next 에 evenHead를 연결해 주면 끝이다.
class Solution {
public ListNode oddEvenList(ListNode head) {
if (head == null) {
return null;
}
ListNode odd = head;
ListNode even = head.next, evenHead = head.next;
while(odd != null && odd.next != null && even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}시간 복잡도 O(n), 공간 복잡도 O(1).
2130. Maximum Twin Sum of a Linked List
노드 수가 n(짝수)개인 Linked list에서, i 번째 노드와 n-1-i 번째 노드를 twin이라고 하자. 이 twin의 합 중에서 가장 큰 값을 찾아라.
In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.
For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.
The twin sum is defined as the sum of a node and its twin.
Given the head of a linked list with even length, return the maximum twin sum of the linked list.
문제를 풀면서 힌트를 확인했는데, 링크드 리스트의 가운데로 가서 뒤쪽 절반(secondHalf)의 리스트를 reverse한 뒤, 두 리스트(firstHalf, secondHalf)를 순회하면서 twin sum을 구하면 공간 복잡도 O(1), 시간 복잡도 O(n)으로 문제를 풀 수 있다.
리스트의 노드 수가 짝수 일 때, two pointer(fast, slow)를 활용해서 가운데에 가면 그 노드는 n/2+1번째가 된다. 그래서 그 노드를 head로 삼아서 reverse를 하면 된다.
class Solution {
public int pairSum(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = reverse(slow);
ListNode firstHalf = head;
int maxTwin = 0;
while(firstHalf != null && secondHalf != null) {
maxTwin = Math.max(maxTwin, firstHalf.val + secondHalf.val);
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return maxTwin;
}
private ListNode reverse(ListNode node) {
ListNode cur = node;
ListNode prev = null;
while(cur != null) {
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}이 코드에서 firstHalf는 n/2+1까지 이어져있어서 while문 조건에서 firstHalf, secondHalf 둘 다 null이 아닐 때까지 twin sum을 구하도록 했다.
1448. Count Good Nodes in Binary Tree
주어진 이진 트리에서 root 노드에서 노드 X로 가는 경로에 X보다 큰 값이 없는 경우 좋은 노드로 정의한다. 주어진 이진트리에서 좋은 노드의 개수를 리턴하는 함수를 작성하라.
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
좋은 노드의 정의에 따라 루트 노드는 항상 좋은 노드이다. (자기 자신밖에 비교할 값이 없음) 그리고 자식 노드로 내려가면서 max 값이 노드 값보다 작거나 같다면 max 값을 업데이트하고, 자식 노드에도 좋은 노드가 있는지 재귀적으로 찾아간다.
class Solution {
public int goodNodes(TreeNode root) {
if (root == null) {
return 0;
}
return goodNodes(root, root.val);
}
private int goodNodes(TreeNode node, int max) {
if (node == null) {
return 0;
}
int sum=0;
if (node.val >= max) {
max = node.val;
sum += 1;
}
return sum + goodNodes(node.left, max) + goodNodes(node.right, max);
}
}이진 트리에 n개의 노드가 있을 때, 모든 노드를 순회하기 때문에 시간 복잡도는 O(n), 공간 복잡도는 트리의 깊이 만큼 재귀적으로 들어가기 때문에 O(logn)이다.
