描述

在一个排序单链表中，删除节点值重复出现的节点，保证每个节点的值只出现一次。

分析

单链表中可以访问到当前节点(curNode)和当前节点的下一个节点（nextNode），根据题意需要判断当前节点值和下一个节点值的两种关系：

1，不相等，当前节点移动到下一个节点，下一个节点移动到当前节点的下一个节点；

2，相等，当前节点的next指针指向nextNode->next，将下一个节点从链表中拆除；更改下一个节点的指向，继续判断；

实现

迭代版，时间复杂度O(n)，空间复杂度O(1)

ListNode *removeDuplicatesFromSortedList(ListNode *head)
{
    ListNode *pCur = head;
    while (pCur->next) {
        ListNode *pNext = pCur->next;
        if (pNext->val == pCur->val) {
            //处理相等的元素
            pCur->next = pNext->next;
            delete pNext;
            continue;
        }
        
        // 处理不相等的情况
        pCur = pNext;
    }
    return head;
}

递归版，时间复杂度O(n)，空间复杂度O(1)

ListNode *removeDuplicatesFromSortedListUseRecursion(ListNode *head)
{
    if (!head->next) {
        return head;
    }
    ListNode *next = head->next;
    
    // 不相等
    if (next->val != head->val) {
        return removeDuplicatesFromSortedListUseRecursion(head->next);
    }
    
    // 相等
    head->next = next->next;
    delete next;
    return removeDuplicatesFromSortedListUseRecursion(head);
}

代码在这儿