Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2
, return 1->2
.
Given 1->1->2->3->3
, return 1->2->3
.
思路:
(1)題意為移除已排序鏈表中重復元素。
(2)首先,對頭結點進行判空,為空則返回空。不為空設定first指向head。
(3)其次,判斷first的後續節點second是否為空,如果不為空,則比較它們值是否相同。如果值不同,則節點first指向second,
second指向first的後續節點,循環繼續;如果值相同,設置節點last指向second的後續節點,如果last不為空,並且last的值
和first的值相同(說明連續三個節點值相同),last指向其後續節點,循環直到ast為空或者first的值和last的值不同,此時,
如果last不為空,則first的後續節點為last,first指向last,second指向first的後續位置,循環繼續,如果last為空,說明已經
遍歷到最後節點,此first的後續節點指向null,返回head。
(4)其指向過程可以簡單如下所示:
例如:1->1->2->3->3->3->4->5->5->5
(A)first=1,second=1,first=second,則last=2,由於first!=last,所以first=2,second=3;
(B)first=2,second=3,first!=second,則first=3,second=3;
(C)first=3,second=3,first=second,則last=3,由於first=last,循環直到last==null或者first!=last,此時last=4,則first=4,second=5;
(D)first=4,second=5,first!=second,則first=5,last=5;
(E)first=5,last=5,first=second,last=5,由於first=last,循環直到last==null或者first!=last,此時last=null,則first.next=null,返回head。
算法代碼實現如下:
public ListNode deleteDuplicates(ListNode head) { if (head == null) return null; ListNode first = head; ListNode second = first.next; while (second != null) { if (first.val == second.val) { ListNode last = second.next; while (last != null && first.val == last.val) { last = last.next; } if (last != null) { first.next = last; first = last; second = first.next; } else { first.next=null; return head; } } else { first = second; second = first.next; } } return head; }