---恢复内容开始---

 Remove Duplicates from Sorted List

题目意图：删除掉linked list里面的重复的元素

思路： 1. 对于重复的点，会保留当前数字第一次出现的点，所以返回结果的起始点与当前起始点为同一个点，不需要新建dummy node来表示起始点。

   　　 2. 用一个pre pointer遍历整个linked list，如果当前点与下一个点一致则删除下一个点。

我的代码：

1  public static ListNode deleteDuplicates(ListNode head) {  2         // write your code here 3         if (head == null) { 4             return head; 5         } 6          7         ListNode pre = new ListNode(0); 8         pre = head; 9         while (pre != null && pre.next != null) {10             while(pre.next != null && pre.next.val == pre.val){11                 pre.next = pre.next.next;12             }13             pre = pre.next;14         }15         return head;16     }

九章代码：

public ListNode deleteDuplicates(ListNode head) {        if (head == null) {            return null;        }        ListNode node = head;        while (node.next != null) {            if (node.val == node.next.val) {                node.next = node.next.next;            } else {                node = node.next;            }        }        return head;    }

反思：1. 对于一维的linked list，只需要分当前点和下一个点是否相同，做一次遍历就好。

　　　2. 对于我的方法，在内层while之行删除所有可能与当前点一致点后，把pre指针往后移。注意要判断是否已经到linked list的结尾。

 Remove Duplicates from Sorted List II

 题目意图：删除所有重复的点

思路：1. 对于重复的点，所有与当前点相等的点全部删除，包括当前点。这样就不能保证head与返回时候的head一致。因为head可能被删除，所以需要建立一个dummy node 放在当前的head前面。

　　　2.因为当数相等时，要删除掉比较者和被比较者，故不能只通过一次循环两两比较。（aaa形式，删掉aa，没法判断。 如果用临时变量记录pre值，那么第一次删除2个点，后来每一次删除1个点，不好控制）所以，用2层while的结构，如果碰到相同的，那么用第二层循环把所有相同的值都删掉。

我的代码：

1 public class Solution { 2     public static ListNode deleteDuplicates(ListNode head) { 3         if (head == null) { 4             return head; 5         } 6         ListNode dummy = new ListNode(0); 7         dummy.next = head; 8         ListNode pre = new ListNode(0); 9         pre = dummy; 10         while (head.next != null) {11             if (head.val == head.next.val) {12                 while (head.next != null && head.val == head.next.val) {13                     head.next = head.next.next;14                 }15                 pre.next = head.next;16                 if(pre.next != null){17                     head = pre.next;18                 }19             } else {20                     head = head.next;21                     pre = pre.next;22             }23         }24             return dummy.next;25     }    26 }

 用了dummy和pre pointer，dummy pointer用于存储整个linked list删除后的头，pre pointer用于存储内部循环被对比节点的前一个点（eg： abc 循环到b与c比较时，pre纪录a，防止b和c相同，同时被删除）。

删除时候，外部循环用于遍历整个linked list。内部循环用于对制定节点遍历后面的所有节点，如果相同删除后面的这个节点，循环中每次只删除后面的这一个节点。对于被比较的这个节点，在内部while循环结束时删除，同时pre pointer不变，更新head节点。

九章代码：

public class Solution {    public ListNode deleteDuplicates(ListNode head) {        if(head == null || head.next == null)            return head;                ListNode dummy = new ListNode(0);        dummy.next = head;        head = dummy;        while (head.next != null && head.next.next != null) {            if (head.next.val == head.next.next.val) {                int val = head.next.val;                while (head.next != null && head.next.val == val) {                    head.next = head.next.next;                }                        } else {                head = head.next;            }        }                return dummy.next;    }}

九章的代码中内部循环的方式更加简单

用head pointer 当作pre pointer，对head->next和head->next 做对比

在外部循环一旦确定2个值相等，用一个val的临时变量纪录当前的值，然后从head->next开始一个一个的向后删除。这样做避免了在内部循环时候需要一一个删除，最后删除当前被比较的node的情况。 因此在内部循环，始终只考虑是否相等，一次删除一个节点。

反思： 多重循环时候，尽量保持一重循环只做一件事情，使得代码简化。对于我的方法中的比较数和被比较数均可通过一个point的next和next next来表示，可以不用2个变量。

 

　　　

 

 

 

 

 

---恢复内容结束---