删除連結清單中所有重複結點,重複結點不保留
分析:
定義一個假的結點頭,将所有的不重複的結點串在其後面,最後傳回該假的結點頭的next就可以了。
在這個題裡面,難點是如何将所有的重複結點都跳過去?
因為重複的結點不止兩個,可能有是三個,四個等等,因為不知道要跳過多少個重複的結點,是以在這裡需要用到一個while循環。
程式:
public Node deleteDuplication() {
Node fakeHead = new Node(-1); //定義的虛拟結點,其中所有不重複的結點都串在後面
Node lastNode = fakeHead ; //記錄新連結清單的尾巴
Node cur = this.head;
//周遊原單連結清單,周遊的結束條件
while (cur != null) {
if (cur.next != null && cur.data == cur.next.data) {
//因為裡面的重複元素可能有多個,是以需要再寫一個循環,讓cur走。同時cur可能為空,是以cur的next可能造成空指針異常。
while (cur.next != null&& cur.data == cur.next.data ) {
cur = cur.next;
}
cur = cur.next; //出來循環之後還應該再走一步,因為此時還沒有完全跳過重複結點。
lastNode .next = cur; //因為過了上一組重複的結點之後,後面可能還會存在重複的結點,
// 是以暫時先将cur綁起來,但是lastNode不能向後移,向後移了就相當于将後面的結點直接串 起來了。
} else {
//确定不重複的結點,挂在虛拟結點後面。
lastNode .next = cur;
lastNode = lastNode .next;
cur = cur.next;
}
}
return fakeHead .next;
}