Linked List - Remove Duplicates from Sorted List

by LauCyun Sep 18,2014 10:42:49 3,503 views

Question

Problem Statement

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

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

题解

遍历之,遇到当前节点和下一节点的值相同时,删除下一节点,并将当前节点next值指向下一个节点的next, 当前节点首先保持不变,直到相邻节点的值不等时才移动到下一节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

/***
 * Remove Duplicates from Sorted List.
 *  Given a sorted linked list, delete all duplicates such that each element appear only once.
 *  For example,
 *  Given 1->1->2, return 1->2.
 *  Given 1->1->2->3->3, return 1->2->3.
 * @param phead: The linked list of headers.
 * @return: The linked list of headers.
 */
struct ListNode *deleteDuplicates(struct ListNode *head) {
    if (head == NULL) {
        return NULL;
    }

    struct ListNode *curr = head;
    while (curr != NULL) {
        while (curr->next != NULL && curr->val == curr->next->val) {
            struct ListNode *temp = curr->next;
            curr->next = curr->next->next;
            temp->next = NULL;
            free(temp);
        }
        curr = curr->next;
    }
    return head;
}

源码分析

  1. 首先进行异常处理,判断phead是否为NULL
  2. 遍历链表,curr->val == curr->next->val时,保存curr->next,便于后面释放内存(非C/C++无需手动管理内存)
  3. 不相等时移动当前节点至下一节点,注意这个步骤必须包含在else中,否则逻辑较为复杂

while 循环处也可使用curr != null && curr.next != null, 这样就不用单独判断head 是否为空了,但是这样会降低遍历的效率,因为需要判断两处。使用双重while循环可只在内循环处判断,避免了冗余的判断。

复杂度分析

遍历链表一次,时间复杂度为\( O(n)\), 使用了一个中间变量进行遍历,空间复杂度为\( O(1)\).

Tags