RemoveNthNodeFromEndOfList

realDuYuanChao · realDuYuanChao · commit 159c520ca044 · 2020-10-06T11:26:14.000+08:00
diff --git a/src/main/java/com/examplehub/leetcode/ListNode.java b/src/main/java/com/examplehub/leetcode/ListNode.java
@@ -0,0 +1,18 @@
+package com.examplehub.leetcode;
+
+public class ListNode {
+    public int val;
+    public ListNode next;
+
+    public ListNode() {
+    }
+
+    public ListNode(int val) {
+        this.val = val;
+    }
+
+    ListNode(int val, ListNode next) {
+        this.val = val;
+        this.next = next;
+    }
+}
diff --git a/src/main/java/com/examplehub/leetcode/middle/RemoveNthNodeFromEndOfList.java b/src/main/java/com/examplehub/leetcode/middle/RemoveNthNodeFromEndOfList.java
@@ -0,0 +1,32 @@
+package com.examplehub.leetcode.middle;
+
+import com.examplehub.leetcode.ListNode;
+
+/**
+ * https://leetcode.com/problems/remove-nth-node-from-end-of-list/
+ */
+public class RemoveNthNodeFromEndOfList {
+    public static ListNode solution1(ListNode head, int n) {
+        int length = 0;
+
+        /* calculate length of list */
+        ListNode current = head;
+        while (current != null) {
+            length++;
+            current = current.next;
+        }
+
+        if (length <= 1) {
+            head = null;
+        } else if (length == n) {
+            head = head.next;
+        } else {
+            current = head;
+            for (int i = 1; i <= length - n - 1; i++) {
+                current = current.next;
+            }
+            current.next = current.next.next;
+        }
+        return head;
+    }
+}
diff --git a/src/main/java/com/examplehub/utils/NodeUtils.java b/src/main/java/com/examplehub/utils/NodeUtils.java
@@ -0,0 +1,34 @@
+package com.examplehub.utils;
+
+import com.examplehub.leetcode.ListNode;
+
+import java.util.StringJoiner;
+
+public class NodeUtils {
+    public static String toString(ListNode head) {
+        ListNode current = head;
+        StringJoiner joiner = new StringJoiner("->");
+        while (current != null) {
+            joiner.add(current.val + "");
+            current = current.next;
+        }
+        joiner.add("NULL");
+        return joiner.toString();
+    }
+
+    public static ListNode makeList(int... numbers) {
+        ListNode head = null;
+        ListNode tail = null;
+        for (int number : numbers) {
+            ListNode newNode = new ListNode(number);
+            newNode.next = null;
+            if (head == null) {
+                tail = head = newNode;
+            } else {
+                tail.next = newNode;
+                tail = tail.next;
+            }
+        }
+        return head;
+    }
+}
diff --git a/src/test/java/com/examplehub/leetcode/middle/RemoveNthNodeFromEndOfListTest.java b/src/test/java/com/examplehub/leetcode/middle/RemoveNthNodeFromEndOfListTest.java
@@ -0,0 +1,34 @@
+package com.examplehub.leetcode.middle;
+
+import com.examplehub.leetcode.ListNode;
+import com.examplehub.utils.NodeUtils;
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+class RemoveNthNodeFromEndOfListTest {
+
+    @Test
+    void testSolution1() {
+        ListNode head = NodeUtils.makeList(1, 2, 3, 4, 5);
+        assertEquals("1->2->3->4->5->NULL", NodeUtils.toString(head));
+
+        head = RemoveNthNodeFromEndOfList.solution1(head, 2);
+        assertEquals("1->2->3->5->NULL", NodeUtils.toString(head));
+
+        head = NodeUtils.makeList(1, 2);
+        assertEquals("1->2->NULL", NodeUtils.toString(head));
+        head = RemoveNthNodeFromEndOfList.solution1(head, 1);
+        assertEquals("1->NULL", NodeUtils.toString(head));
+
+        head = NodeUtils.makeList(1);
+        assertEquals("1->NULL", NodeUtils.toString(head));
+        head = RemoveNthNodeFromEndOfList.solution1(head, 1);
+        assertEquals("NULL", NodeUtils.toString(head));
+
+        head = NodeUtils.makeList(1, 2);
+        assertEquals("1->2->NULL", NodeUtils.toString(head));
+        head = RemoveNthNodeFromEndOfList.solution1(head, 2);
+        assertEquals("2->NULL", NodeUtils.toString(head));
+    }
+}
