程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode 83 Remove Duplicates from Sorted List(從已排序鏈表中移除重復元素)(*)

LeetCode 83 Remove Duplicates from Sorted List(從已排序鏈表中移除重復元素)(*)

編輯:關於C++

翻譯

給定一個已排序鏈表,刪除所有重復元素讓每個元素只出現一次。

例如:
給定 1->1->2, 返回 1->2。
給定 1->1->2->3->3, 返回 1->2->3。

原文

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.

分析

切入正題,首先我們應該先判斷是否為空:

if (head == NULL) return NULL;
if (head->next == NULL) return head;    

但是這兩行代碼是可以簡寫的:

if (head == NULL || head->next == NULL) return head;

下面是一個循環語句:

while (head->next) {
    if (head->val == head->next->val) {
        head->next = head->next->next;
    }
    else {
        head = head->next;
    }   
}    

意思非常簡單,首先判斷當前的節點的值與下一個節點的值是否相等,如果相等,則將下下一個節點賦值給下一個節點。

1——1——2——3——3
改寫成:
1——2——3——3

此時head還在1上,但為什麼不將其移動到2上呢,也就是說代碼為什麼不是這樣的:

while (head->next) {
    if (head->val == head->next->val) {
        head->next = head->next->next;
        head = head->next;
    }
    else {
        head = head->next;
    }   
}    

理由很簡單,例如:

1——1——1——2——3——3
經過第一次變換後:
1——1——2——3——3
如果貿然將head移動到下一個節點上,那麼下一次的對比就是對比1和2了,顯然是不合理的。

到了這裡移除操作就已經完成了,但是能夠直接returnhead嗎,顯然也是不能的,因為head已經移動到了最後一個節點了。

所以應該在while循環之前就設置了新的head作為記錄,最後返回它就好了。

ListNode* newHead = head;
while(){}
return newHead;

代碼

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* newNode = head;
        while (head->next) {
            if (head->val == head->next->val)
                head->next = head->next->next;
            else
                head = head->next;
        }
        return newNode;
    }
};
 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved