題目描述

在一個(gè)排序的鏈表中，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留，返回鏈表頭指針。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

題解：

int value用來(lái)存儲(chǔ)當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)值，創(chuàng)建一個(gè)新的鏈表節(jié)點(diǎn)用于連接符合存儲(chǔ)條件的節(jié)點(diǎn)；比較當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)值和當(dāng)前節(jié)點(diǎn)的值是否相等；用tip記錄狀態(tài)int tip=0，節(jié)點(diǎn)值相等：tip=1；節(jié)點(diǎn)值不等：tip=0；

1. 當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的值不等時(shí)：
   如果tip=0，說(shuō)明上次判斷時(shí)節(jié)點(diǎn)值也不等，所以當(dāng)前節(jié)點(diǎn)與上一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)值也不相等，可以連接該節(jié)點(diǎn)；
   如果tip=1，說(shuō)明上次判斷時(shí)節(jié)點(diǎn)值相等，此時(shí)我們只需要更新value，讓它等于下一個(gè)節(jié)點(diǎn)的值即可；
2. 當(dāng)前節(jié)點(diǎn)與下一個(gè)節(jié)點(diǎn)的值相等時(shí)：
   將tip狀態(tài)更改為1；
3. 考慮邊界條件，當(dāng)前節(jié)點(diǎn)是尾節(jié)點(diǎn)時(shí)：
   根據(jù)tip判斷出當(dāng)前節(jié)點(diǎn)和上一個(gè)節(jié)點(diǎn)是否相等：不等的話讓新節(jié)點(diǎn)的next連接該節(jié)點(diǎn)；相等則令新節(jié)點(diǎn)的next指向NULL；

My Solution（C/C++完整實(shí)現(xiàn)）：

#include <cstdio>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode * deleteDuplication(ListNode* pHead) {
        ListNode result(0);
        ListNode *new_head = &result;
        int value = pHead->val;
        int tip = 0;
        while (pHead) {
            if (pHead->next && pHead->next->val == value) {
                tip = 1;
            }
            else if(pHead->next && pHead->next->val != value) {
                if (tip == 0) {
                    //可以存節(jié)點(diǎn)！
                    new_head->next = pHead;
                    new_head = new_head->next;
                }
                value = pHead->next->val;
                tip = 0;
            }
            else {
                if (tip == 0) {
                    new_head->next = pHead;
                }
                else {
                    new_head->next = NULL;
                }

            }
            pHead = pHead->next;
        }
        return result.next;
    }
};

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(3);
    ListNode e(4);
    ListNode f(5);
    ListNode g(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    Solution s;
    ListNode *result = s.deleteDuplication(&a);
    while (result) {
        printf("%d->", result->val);
        result = result->next;
    }
    return 0;
}

結(jié)果：

1->2->4->