面试题 02.01. 移除重复节点中,一看到去重,立马就想到了hashset进行去重,因此在开始解答的时候使用hashset很快写出来,在最初的测试中也是没问题,一提交就发现了wa声一片,其中原因在于测试的时候样本不够,都使用了有序的链表,但是在hashset进行去重的时候,恰好也是去重+排序,对应原文要求保持最开始出现的顺序,因此简单使用hashset方法是不行的
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeDuplicateNodes(ListNode head) { Set<Integer> st = new HashSet<>(); ListNode ln = head; while(ln != null){ st.add(ln.val); ln = ln.next; } ListNode dummy = new ListNode(0); ListNode newHead = dummy; for(int ste:st){ newHead.next = new ListNode(ste); newHead = newHead.next; } return dummy.next; } }回忆起剑指 Offer 18. 删除链表的节点即有删除相应节点的代码,但是在18题只要求删除一次.不过稍微修改一下删除代码即可,使得可以多次删除重复元素,只需要修改其中一步,保持快慢指针的顺序,即可多次删除
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteNode(ListNode head, int val) { ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode cur = dummyHead; ListNode pre = head; while(pre != null){ if(pre.val == val){ pre = pre.next; cur.next = pre; } else{ cur = pre; pre = pre.next; } } return dummyHead.next; } }参考这道题可以对这道题做类似的处理,但是需要注意保留ln = ln.next;,而不是直接newdummy.next = ln.next,直接使用的话,会使得快慢指针的顺序发生变化,使得在后续删除中失效,不过在18题中无需这样处理
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeDuplicateNodes(ListNode head) { Set<Integer> st = new HashSet<>(); ListNode ln = head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode newdummy = dummy; while(ln != null){ if(st.contains(ln.val)){ ln = ln.next; //这步操作很必要,保持了快慢指针的顺序 newdummy.next = ln; } else{ st.add(ln.val); // newdummy.next = ln; ln = ln.next; newdummy = newdummy.next; } } // System.out.println(st); return dummy.next; } }