Commit2bc2237

committed

add a second solution for 1171

1 parentd8c4ff5 commit2bc2237Copy full SHA for 2bc2237

File tree

+37

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _1171.java
- test/java/com/fishercoder
  - _1171Test.java

+37

-0

lines changed

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -72,4 +72,37 @@ private List<Integer> shrinkList(List<Integer> list) {`
`72`	`72`	`returnlist;`
`73`	`73`	`}`
`74`	`74`	`}`
	`75`	`+`
	`76`	`+publicstaticclassSolution2 {`
	`77`	`+/**`
	`78`	`+ * credit: https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/discuss/366337/Java-Iterative-and-Recursive-solution`
	`79`	`+ * this post explains it all`
	`80`	`+ * key of the hashmap is the prefix sum of all the nodes we've gone so far`
	`81`	`+ * value of the hashmap is the corresponding linked list node`
	`82`	`+ */`
	`83`	`+publicListNoderemoveZeroSumSublists(ListNodehead) {`
	`84`	`+ListNodepre =newListNode(-1);`
	`85`	`+ListNodecurr =pre;`
	`86`	`+pre.next =head;`
	`87`	`+Map<Integer,ListNode>map =newHashMap<>();`
	`88`	`+intpreSum =0;`
	`89`	`+while (curr !=null) {`
	`90`	`+preSum +=curr.val;`
	`91`	`+if (map.containsKey(preSum)) {`
	`92`	`+curr =map.get(preSum).next;`
	`93`	`+intkey =preSum +curr.val;`
	`94`	`+while (key !=preSum) {`
	`95`	`+map.remove(key);`
	`96`	`+curr =curr.next;`
	`97`	`+key +=curr.val;`
	`98`	`+ }`
	`99`	`+map.get(preSum).next =curr.next;`
	`100`	`+ }else {`
	`101`	`+map.put(preSum,curr);`
	`102`	`+ }`
	`103`	`+curr =curr.next;`
	`104`	`+ }`
	`105`	`+returnpre.next;`
	`106`	`+ }`
	`107`	`+ }`
`75`	`108`	`}`

Lines changed: 4 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -10,20 +10,24 @@`
`10`	`10`
`11`	`11`	`publicclass_1171Test {`
`12`	`12`	`privatestatic_1171.Solution1solution1;`
	`13`	`+privatestatic_1171.Solution2solution2;`
`13`	`14`
`14`	`15`	`@BeforeClass`
`15`	`16`	`publicstaticvoidsetup() {`
`16`	`17`	`solution1 =new_1171.Solution1();`
	`18`	`+solution2 =new_1171.Solution2();`
`17`	`19`	`}`
`18`	`20`
`19`	`21`	`@Test`
`20`	`22`	`publicvoidtest1() {`
`21`	`23`	`assertEquals(LinkedListUtils.contructLinkedList(newint[]{3,1}),solution1.removeZeroSumSublists(LinkedListUtils.contructLinkedList(newint[]{1,2, -3,3,1})));`
	`24`	`+assertEquals(LinkedListUtils.contructLinkedList(newint[]{3,1}),solution2.removeZeroSumSublists(LinkedListUtils.contructLinkedList(newint[]{1,2, -3,3,1})));`
`22`	`25`	`}`
`23`	`26`
`24`	`27`	`@Test`
`25`	`28`	`publicvoidtest2() {`
`26`	`29`	`assertEquals(LinkedListUtils.contructLinkedList(newint[]{1,2,4}),solution1.removeZeroSumSublists(LinkedListUtils.contructLinkedList(newint[]{1,2,3, -3,4})));`
	`30`	`+assertEquals(LinkedListUtils.contructLinkedList(newint[]{1,2,4}),solution2.removeZeroSumSublists(LinkedListUtils.contructLinkedList(newint[]{1,2,3, -3,4})));`
`27`	`31`	`}`
`28`	`32`
`29`	`33`	`@Test`

Comments

(0)