Reverse a singly linked list.
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode toBeCurrent = head.next;
ListNode toBePrev = head;
toBePrev.next = null;
while (toBeCurrent != null) {
ListNode temp = toBeCurrent.next;
toBeCurrent.next = toBePrev;
toBePrev = toBeCurrent;
toBeCurrent = temp;
}
return toBePrev;
}
Need to Retry
public ListNode reverseList(ListNode head) {
ListNode first = null;
ListNode second = null;
ListNode third = null;
if (head == null) {
return null;
}
first = head;
if (first.next == null) {
return first;
}
second = first.next;
first.next = null;
if (second.next == null) {
second.next = first;
return second;
}
third = second.next;
while (third != null) {
second.next = first;
first = second;
second = third;
third = second.next;
}
second.next = first;
return second;
}
25분가량 소요
깔끔하게 풀 수 있을 텐데 생각이 들었는데 떠오르지 않아서
일단 머릿속에 아이디어를 구현했고 맞췄다.
다시 풀어봐도 좋을 문제라고 생각이 들었다.
다른 코드를 봤는데 굉장히 깔끔한 코드가 있었다.
참고하도록 하자 !
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode current = head;
while(current != null) {
ListNode temp = current.next;
current.next = prev;
prev = current;
current = temp;
}
return prev;
}
Need to Retry -> 자료구조를 사용해보자.
public ListNode reverseList(ListNode head) {
ListNode l = null;
ListNode r = null;
ListNode m = head;
while (m != null) {
r = m.next;
m.next = l;
l = m;
m = r;
}
return l;
}
Reference Code
public ListNode reverseList(ListNode head) {
//declare Stack
//for each node
// put node in stack
//take first node from stack
//while stack is not empty
//. node .next = stack.pop
//return first Node
if(head == null){
return null;
}
Stack<ListNode> nodes = new Stack<>();
ListNode cur = head;
nodes.push(cur);
while(cur != null){
if(cur.next != null){
nodes.push(cur.next);
}
cur = cur.next;
}
ListNode returnNode = nodes.pop();
ListNode headTemp = returnNode;
while(nodes.size() != 0){
headTemp.next = nodes.pop();
headTemp = headTemp.next;
}
headTemp.next = null;
return returnNode;
}
Stack을 사용하면 자연스럽게 Reverse하게 연결을 할 수가 있다.
굉장히 좋은 접근이라는 생각이 든다.
FeedBack
Iteratively 하게 풀었다.
다른 코드를 보니 Stack을 사용했는데 너무 좋은 접근이었다.
다음엔 Stack 자료구조를 떠올려서 풀어보면 좋을 거 같다.
Write a program that outputs the string representation of numbers from 1 to n.
But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”.
For numbers which are multiples of both three and five output “FizzBuzz”.
n = 15,
Return:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]
public List<String> fizzBuzz(int n) {
List<String> ans = new ArrayList<>();
for (int i = 1; i <= n; i++) {
ans.add(getString(i));
}
return ans;
}
private String getString(int i) {
String fizz = "Fizz";
String buzz = "Buzz";
String fizzBuzz = "FizzBuzz";
if (i % 3 == 0 && i % 5 == 0) {
return fizzBuzz;
} else if (i % 3 == 0) {
return fizz;
} else if (i % 5 == 0) {
return buzz;
} else {
return String.valueOf(i);
}
}
Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list,
instead you will be given access to the node to be deleted directly.
It is guaranteed that the node to be deleted is not a tail node in the list.
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
문제가 뭐지?…
굉장히 어색한 스타일의 문제였다.
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?
Input: nums = [2,2,1]
Output: 1
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
Integer value = map.getOrDefault(nums[i], 0);
map.put(nums[i], value + 1);
}
int ans = 0;
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) == 1) {
ans = nums[i];
break;
}
}
return ans;
}
문제 의도와는 다르게 막 풀었다.
사실 XOR로 푸는게 정확한 답이다.
Feed Back
Case 1
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans ^= nums[i];
}
return ans;
}
XOR은 같으면 0
다르면 1이다.
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans ^= nums[i];
}
return ans;
}
Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array,
you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
public void reverseString(char[] s) {
int length = s.length;
char[] ans = new char[length];
for (int i = 0; i < length; i++) {
ans[i] = s[length - 1 - i];
}
for (int i = 0; i < length; i++) {
s[i] = ans[i];
}
}
막 풀어도 될까 했는데 풀리는구나.
그래도 좋은 코드 참고하자.
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
public int maxDepth(TreeNode root) {
return find(0, root);
}
public int find(int depth, TreeNode node) {
if (node == null) {
return depth;
}
return Math.max(find(depth + 1, node.left), find(depth + 1, node.right));
}
머리 아팠다.
오랜만에 재귀로 푸려니까 너무 어려웠다.
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return getMaxDepth(root, 1);
}
public int getMaxDepth(TreeNode node, int ans) {
if (node == null) {
return ans;
}
int leftMaxDepth = 0;
int rightMaxDepth = 0;
if (node.left != null) {
leftMaxDepth = getMaxDepth(node.left, ans + 1);
System.out.println("leftMaxDepth : " + leftMaxDepth);
}
if (node.right != null) {
rightMaxDepth = getMaxDepth(node.right, ans + 1);
System.out.println("rightMaxDepth : " + rightMaxDepth);
}
ans = Math.max(ans, Math.max(leftMaxDepth, rightMaxDepth));
return ans;
}
}
LeetCode 웹 IDE에서 바로 풀었다.
풀 수 있을까? 했는데 두드려보니 풀렸다.
class Solution {
public int maxDepth(TreeNode root) {
return go(root,0,0);
}
private int go(TreeNode node, int depth, int ans) {
if (node == null) {
return depth;
}
ans = Math.max(ans, go(node.left, depth+1, ans));
ans = Math.max(ans, go(node.right, depth+1, ans));
return ans;
}
}