题目描述

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given1->1->2, return1->2.
Given1->1->2->3->3, return1->2->3.

题目大意

给定一个有序链表，删除其中重复元素，仅剩下一个。
如例子所见。

第一种方法

思路

维护两个指针，前指针负责向后遍历，后指针负责连接不重复的元素。
注意delete操作，以防止内存泄漏。

代码

#include<iostream>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
typedef ListNode* list_node; // 别名
ListNode *deleteDuplicates(ListNode *head)
{
    if(head == NULL)return NULL;
    list_node p1 = head;
    list_node p2 = head->next;
    while(p2)
    {
        // 值相等
        if(p1->val == p2->val)
        {
            p1->next = NULL; // 暂且先把p1的next置为NULL
            list_node tmp = p2; // 暂存p2
            p2 = p2->next; // p2指针后移
            delete tmp;
        }
        else
        {
            p1->next = p2;
            p1 = p1->next;
            p2 = p2->next;
        }
    }

    return head;
}

int main()
{
    list_node p1, p2, p3, p4, p5;

    p1 = new ListNode(1);
    p2 = new ListNode(1);
    p3 = new ListNode(2);
    p4 = new ListNode(3);
    p5 = new ListNode(3);

    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = p5;

    p1 = deleteDuplicates(p1);

    while(p1)
    {
        cout << p1->val << ' ';
        p1 = p1->next;
    }

    return 0;
}

运行结果

第二种方法

思路

思路跟第一种并无大的区别。

代码

typedef ListNode* list_node; // 别名
ListNode *deleteDuplicates(ListNode *head)
{
    if(head == NULL)return head;
    list_node cur = head;
    while(cur != NULL)
    {
        while(cur->next != NULL && cur->val == cur->next->val)
        {
            list_node tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        }
        cur = cur->next;
    }
    return head;
}

运行结果

以上。