天天看點

删除連結清單中所有重複結點,重複結點不保留

删除連結清單中所有重複結點,重複結點不保留

分析:

定義一個假的結點頭,将所有的不重複的結點串在其後面,最後傳回該假的結點頭的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;
    }
           

繼續閱讀