Linked List - Remove All Duplicates from Sorted List

by LauCyun Sep 18,2014 14:26:01 1,691 views

Question

Problem Statement

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题解

单链表 - 删除有序链表的重复节点(Remove Duplicates from Sorted List)为保留重复值节点的一个,这题删除全部重复节点,看似区别不大,但是考虑到链表头不确定(可能被删除,也可能保留),因此若用传统方式需要较多的if条件语句。这里介绍一个处理链表头节点不确定的方法——引入dummy node.

struct ListNode *dummy =newNode(-1);
dummy->next = head;
struct ListNode *curr = dummy;

引入新的指针变量dummy,并将其next变量赋值为head,考虑到原来的链表头节点可能被删除,故应该从dummy处开始处理,这里复用了head变量。考虑链表A->B->C,删除B时,需要处理和考虑的是A和C,将A的next指向C。如果从空间使用效率考虑,可以使用head代替以上的curr,含义一样,node比较好理解点。

单链表 - 删除有序链表的重复节点(Remove Duplicates from Sorted List)不同的是,由于此题引入了新的节点dummy,不可再使用node->val == node->next->val,原因有二:

  1. 此题需要将值相等的节点全部删掉,而删除链表的操作与节点前后两个节点都有关系,故需要涉及三个链表节点。且删除单向链表节点时不能删除当前节点,只能改变当前节点的next指向的节点。
  2. 在判断val是否相等时需先确定node->nextnode->next->next均不为空,否则不可对其进行取值。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Create a new list node.
 * @param val: The value of the new node.
 * @return
 */
struct ListNode *newNode(const int val) {
    struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
    temp->val = val;
    temp->next = NULL;
    return temp;
}

/***
 * Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
 *  For example,
 *  Given 1->2->3->3->4->4->5, return 1->2->5.
 *  Given 1->1->1->2->3, return 2->3.
 *
 * @param head: The linked list of headers.
 * @return: The linked list of headers.
 */
struct ListNode *deleteAllDuplicates(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    struct ListNode *dummy =newNode(-1);
    dummy->next = head;
    struct ListNode *curr = dummy;
    while (curr->next != NULL && curr->next->next != NULL) {
        if (curr->next->val == curr->next->next->val) {
            int tempVal = curr->next->val;
            // remove ListNode curr->next
            while (curr->next != NULL && tempVal == curr->next->val) {
                struct ListNode *temp = curr->next;
                curr->next = curr->next->next;
                free(temp);
            }
        }
        else {
            curr = curr->next;
        }
    }
    // do not forget free dummy
    head = dummy->next;
    free(dummy);
    return head;
}

源码分析

  1. 首先考虑异常情况,headNULLhead->nextNULL 时返回 head
  2. new一个dummy变量,dummy->next指向原链表头。
  3. 使用新变量curr并设置其为dummy头节点,遍历用。
  4. 当前节点和下一节点val相同时先保存当前值tempVal,便于while循环终止条件判断和删除节点。注意这一段代码也比较精炼。
  5. 最后返回dummy->next,即题目所要求的头节点。

Python 中也可不使用is not None判断,但是效率会低一点。具体过程如图:

复杂度分析

两根指针(curr.nextcurr.next.next)遍历,时间复杂度为\( O(2n)\)。使用了一个 dummy 和中间缓存变量,空间复杂度近似为\(O(1)\)

Tags