剑指offer-删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

题解：

int value用来存储当前节点的节点值，创建一个新的链表节点用于连接符合存储条件的节点；比较当前节点的下一个节点值和当前节点的值是否相等；用tip记录状态int tip=0，节点值相等：tip=1；节点值不等：tip=0；

1. 当前节点与下一个节点的值不等时：
   如果tip=0，说明上次判断时节点值也不等，所以当前节点与上一个节点的节点值也不相等，可以连接该节点；
   如果tip=1，说明上次判断时节点值相等，此时我们只需要更新value，让它等于下一个节点的值即可；
2. 当前节点与下一个节点的值相等时：
   将tip状态更改为1；
3. 考虑边界条件，当前节点是尾节点时：
   根据tip判断出当前节点和上一个节点是否相等：不等的话让新节点的next连接该节点；相等则令新节点的next指向NULL；

My Solution（C/C++完整实现）：

#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) {
                    //可以存节点！
                    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;
}

结果：

1->2->4->