N-th Element of a Linked List (Java)
Implement a function that finds the nth node in a linked list, counting from the end.
Your function should take a linked list (its head element) and n, a positive integer as its arguments.
Examples:
head = 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null / None)
The third element of head counting from the end is 3.
head2 = 1 -> 2 -> 3 -> 4 -> (null / None)
The fourth element of head2 counting from the end is 1.
If the given n is larger than the number of nodes in the list, return null / None.
풀이
head가 null 이면 n에 어떤 숫자가 들어가도 null 이기 때문에 먼저 null 체크를 먼저 해준다.
End(끝)에서부터 n만큼 다시 거슬러 올라오기 때문에
Stack을 이용해(LIFO) n만큼 pop 해주면 거슬러 올라오는 것과 같은 효과가 나타남
package com.company;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
// NOTE: The following input values will be used for testing your solution.
Node current = new Node(1, null);
for (int i = 2; i < 8; i++) {
current = new Node(i, current);
}
Node head = current;
// head = 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null)
Node current2 = new Node(4, null);
for (int i = 3; i > 0; i--) {
current2 = new Node(i, current2);
}
Node head2 = current2;
// head2 = 1 -> 2 -> 3 -> 4 -> (null)
nthFromLast(head, 1);
// should return 1.
// nthFromLast(head, 5) should return 5.
// nthFromLast(head2, 2) should return 3.
// nthFromLast(head2, 4) should return 1.
// nthFromLast(head2, 5) should return null.
// nthFromLast(null, 1) should return null.
}
// Implement your solution below.
public static Node nthFromLast(Node head, int n) {
if (head == null)
return null;
Stack<Node> nodeStack = new Stack<>();
while (head != null) {
nodeStack.push(head);
head = head.child;
}
if (nodeStack.size() >= n)
for (int i = 0; i < n; i++) {
head = nodeStack.pop();
}
return head;
}
// NOTE: Feel free to use the following function for testing.
// It converts the given linked list into an easy-to-read string format.
// Example: 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null)
public static String linkedListToString(Node head) {
Node current = head;
StringBuilder sb = new StringBuilder();
while (current != null) {
sb.append(String.valueOf(current.value));
sb.append(" -> ");
current = current.child;
}
sb.append("(null)");
return sb.toString();
}
}
강사풀이
매번 느끼는거지만 index를 정말 잘 활용하는 거 같다.
left와 right으로 나누어 비교하는 방식으로 풀이를 했다.
public class Nth {
public static void main(String[] args) {
// NOTE: The following input values will be used for testing your solution.
Node current = new Node(1, null);
for (int i = 2; i < 8; i++) {
current = new Node(i, current);
}
Node head = current;
// head = 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null)
Node current2 = new Node(4, null);
for (int i = 3; i > 0; i--) {
current2 = new Node(i, current2);
}
Node head2 = current2;
// head2 = 1 -> 2 -> 3 -> 4 -> (null)
// nthFromLast(head, 1) should return 1.
// nthFromLast(head, 5) should return 5.
// nthFromLast(head2, 2) should return 3.
// nthFromLast(head2, 4) should return 1.
// nthFromLast(head2, 5) should return null.
// nthFromLast(null, 1) should return null.
}
// Implement your function below.
public static Node nthFromLast(Node head, int n) {
Node left = head;
Node right = head;
// First, make sure that we have at least n items in the linked list.
for (int i = 0; i < n; i++) {
if (right == null) return null;
right = right.child;
}
while (right != null) {
right = right.child;
left = left.child;
}
return left;
}
// NOTE: Feel free to use the following function for testing.
// It converts the given linked list into an easy-to-read string format.
// Example: 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null)
public static String linkedListToString(Node head) {
Node current = head;
StringBuilder sb = new StringBuilder();
while (current != null) {
sb.append(String.valueOf(current.value));
sb.append(" -> ");
current = current.child;
}
sb.append("(null)");
return sb.toString();
}
}