swapping-nodes-in-a-linked-list (examplehub#97)

realDuYuanChao · github-actions · web-flow · commit 36f94e985c6e · 2021-04-06T20:35:01.000+08:00
* remove-linked-list-elements

* swapping-nodes-in-a-linked-list

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/src/main/java/com/examplehub/leetcode/easy/RemoveLinkedListElements.java b/src/main/java/com/examplehub/leetcode/easy/RemoveLinkedListElements.java
@@ -0,0 +1,28 @@
+package com.examplehub.leetcode.easy;
+
+import com.examplehub.leetcode.ListNode;
+
+/** https://leetcode.com/problems/remove-linked-list-elements/ */
+public class RemoveLinkedListElements {
+  public static ListNode solution1(ListNode head, int val) {
+    ListNode header = new ListNode();
+    header.next = head;
+    ListNode cur = header;
+    while (cur.next != null) {
+      if (cur.next.val == val) {
+        cur.next = cur.next.next;
+      } else {
+        cur = cur.next;
+      }
+    }
+    return header.next;
+  }
+
+  public static ListNode solution2(ListNode head, int value) {
+    if (head == null) {
+      return null;
+    }
+    head.next = solution2(head.next, value);
+    return head.val == value ? head.next : head;
+  }
+}
diff --git a/src/main/java/com/examplehub/leetcode/middle/AddTwoNumbers.java b/src/main/java/com/examplehub/leetcode/middle/AddTwoNumbers.java
@@ -1,5 +1,7 @@
 package com.examplehub.leetcode.middle;
 
+import com.examplehub.leetcode.ListNode;
+
 /** https://leetcode.com/problems/add-two-numbers/ */
 public class AddTwoNumbers {
 
@@ -61,19 +63,3 @@ public static ListNode solution2(ListNode l1, ListNode l2) {
     return dummyHead.next;
   }
 }
-
-class ListNode {
-  int val;
-  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/SwappingNodesInALinkedList.java b/src/main/java/com/examplehub/leetcode/middle/SwappingNodesInALinkedList.java
@@ -0,0 +1,24 @@
+package com.examplehub.leetcode.middle;
+
+import com.examplehub.leetcode.ListNode;
+import com.examplehub.utils.NodeUtils;
+
+/** https://leetcode.com/problems/swapping-nodes-in-a-linked-list/ */
+public class SwappingNodesInALinkedList {
+  public static ListNode solution1(ListNode head, int k) {
+    int length = NodeUtils.length(head);
+
+    ListNode p1 = head;
+    ListNode p2 = head;
+    for (int i = 1; i <= length - k; ++i) {
+      if (i <= k - 1) {
+        p1 = p1.next;
+      }
+      p2 = p2.next;
+    }
+    int t = p1.val;
+    p1.val = p2.val;
+    p2.val = t;
+    return head;
+  }
+}
diff --git a/src/main/java/com/examplehub/utils/NodeUtils.java b/src/main/java/com/examplehub/utils/NodeUtils.java
@@ -30,4 +30,14 @@ public static ListNode makeList(int... numbers) {
     }
     return head;
   }
+
+  public static int length(ListNode head) {
+    int count = 0;
+    ListNode cur = head;
+    while (cur != null) {
+      cur = cur.next;
+      count++;
+    }
+    return count;
+  }
 }
diff --git a/src/test/java/com/examplehub/leetcode/easy/RemoveLinkedListElementsTest.java b/src/test/java/com/examplehub/leetcode/easy/RemoveLinkedListElementsTest.java
@@ -0,0 +1,33 @@
+package com.examplehub.leetcode.easy;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.examplehub.leetcode.ListNode;
+import com.examplehub.utils.NodeUtils;
+import org.junit.jupiter.api.Test;
+
+class RemoveLinkedListElementsTest {
+  @Test
+  void testSolution1() {
+    ListNode head = NodeUtils.makeList(1, 2, 6, 3, 4, 5, 6);
+    assertEquals("1->2->3->4->5", RemoveLinkedListElements.solution1(head, 6).toString());
+
+    head = NodeUtils.makeList();
+    assertSame(null, RemoveLinkedListElements.solution1(head, 1));
+
+    head = NodeUtils.makeList(7, 7, 7, 7);
+    assertSame(null, RemoveLinkedListElements.solution1(head, 7));
+  }
+
+  @Test
+  void testSolution2() {
+    ListNode head = NodeUtils.makeList(1, 2, 6, 3, 4, 5, 6);
+    assertEquals("1->2->3->4->5", RemoveLinkedListElements.solution2(head, 6).toString());
+
+    head = NodeUtils.makeList();
+    assertSame(null, RemoveLinkedListElements.solution2(head, 1));
+
+    head = NodeUtils.makeList(7, 7, 7, 7);
+    assertSame(null, RemoveLinkedListElements.solution2(head, 7));
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/middle/AddTwoNumbersTest.java b/src/test/java/com/examplehub/leetcode/middle/AddTwoNumbersTest.java
@@ -2,6 +2,7 @@
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
 
+import com.examplehub.leetcode.ListNode;
 import org.junit.jupiter.api.Test;
 
 class AddTwoNumbersTest {
diff --git a/src/test/java/com/examplehub/leetcode/middle/SwappingNodesInALinkedListTest.java b/src/test/java/com/examplehub/leetcode/middle/SwappingNodesInALinkedListTest.java
@@ -0,0 +1,28 @@
+package com.examplehub.leetcode.middle;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.examplehub.leetcode.ListNode;
+import com.examplehub.utils.NodeUtils;
+import org.junit.jupiter.api.Test;
+
+class SwappingNodesInALinkedListTest {
+  @Test
+  void testSolution1() {
+    ListNode head = NodeUtils.makeList(1, 2, 3, 4, 5);
+    assertEquals("1->4->3->2->5", SwappingNodesInALinkedList.solution1(head, 2).toString());
+
+    head = NodeUtils.makeList(7, 9, 6, 6, 7, 8, 3, 0, 9, 5);
+    assertEquals(
+        "7->9->6->6->8->7->3->0->9->5", SwappingNodesInALinkedList.solution1(head, 5).toString());
+
+    head = NodeUtils.makeList(1);
+    assertEquals("1", SwappingNodesInALinkedList.solution1(head, 1).toString());
+
+    head = NodeUtils.makeList(1, 2);
+    assertEquals("2->1", SwappingNodesInALinkedList.solution1(head, 1).toString());
+
+    head = NodeUtils.makeList(1, 2, 3);
+    assertEquals("1->2->3", SwappingNodesInALinkedList.solution1(head, 2).toString());
+  }
+}
diff --git a/src/test/java/com/examplehub/utils/NodeUtilsTest.java b/src/test/java/com/examplehub/utils/NodeUtilsTest.java
@@ -0,0 +1,20 @@
+package com.examplehub.utils;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import com.examplehub.leetcode.ListNode;
+import org.junit.jupiter.api.Test;
+
+class NodeUtilsTest {
+  @Test
+  void testLength() {
+    ListNode head = NodeUtils.makeList();
+    assertEquals(0, NodeUtils.length(head));
+
+    head = NodeUtils.makeList(1, 2, 3, 4);
+    assertEquals(4, NodeUtils.length(head));
+
+    head = NodeUtils.makeList(6);
+    assertEquals(1, NodeUtils.length(head));
+  }
+}

Original file line number	Diff line number	Diff line change
`@@ -30,4 +30,14 @@ public static ListNode makeList(int... numbers) {`
`30`	`30`	`}`
`31`	`31`	`return head;`
`32`	`32`	`}`
	`33`	`+`
	`34`	`+ public static int length(ListNode head) {`
	`35`	`+ int count = 0;`
	`36`	`+ ListNode cur = head;`
	`37`	`+ while (cur != null) {`
	`38`	`+ cur = cur.next;`
	`39`	`+ count++;`
	`40`	`+ }`
	`41`	`+ return count;`
	`42`	`+ }`
`33`	`43`	`}`