程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

編輯:C++入門知識

Remove Duplicates from Sorted List


 

 

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;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved