How to eliminate duplicates from a sorted list in LeetCode problem 83?

本文共计795个文字，预计阅读时间需要4分钟。

题目描述：给定一个已排序的链表，删除所有重复元素，使得每个元素只出现一次。例如：输入：1-1-2 输出：1-2

思路解析：该问题只需要两个指针prev和cur即可。为什么不需要next指针呢？

解题思路：

1.初始化两个指针prev和cur，prev指向链表头部，cur指向链表头部。

2.遍历链表，当cur不为空时，执行以下操作：

a. 如果cur的下一个节点值与cur的值相同，则将cur的下一个节点指向cur的下一个节点的下一个节点，并继续移动cur指针。 b. 如果cur的下一个节点值与cur的值不同，则将prev的下一个节点指向cur，并将cur指针向后移动。

3.遍历完成后，返回修改后的链表头部。

题意描述

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

Example 1:

Input: 1->1->2

Output: 1->2

思路解析

该题只需要两个指针，prev和cur即可。为什么不需要nex呢？

这个问题值得思考。

是因为在之前的问题中，cur.next = prev，这样就会导致cur无法后移。而在这个问题中，如果prev.val == cur.val，只是将prev.next = cur.next，并不会影响cur的后移。

C++代码

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}

ListNode* prev = head;
ListNode* cur = head->next;

while (cur) {
if (prev->val == cur->val) {
prev->next = cur->next;
cur = cur->next;
}

else {
prev = cur;
cur = cur->next;
}
}

return head;

}
};

但是这样其实会有个小问题，也就是重复数据节点只是跳过了，并没有释放相应的内存。

这时候就需要用nex保存cur.next。

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}

ListNode* prev = head;
ListNode* cur = head->next;

while (cur) {
if (prev->val == cur->val) {
prev->next = cur->next;
ListNode* nex = cur->next;
cur->next = NULL;
delete(cur);
cur = nex;
}

else {
prev = cur;
cur = cur->next;
}
}

return head;

}
};

Java代码

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
import java.util.*;
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode prev = head;
ListNode cur = head.next;

while (cur != null) {
if (prev.val == cur.val) {
prev.next = cur.next;
cur = prev.next;
}

else {
prev = cur;
cur = cur.next;
}
}

return head;
}
}

Python代码

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""

if head == None or head.next == None:
return head

prev = head
cur = head.next

while cur:
if prev.val == cur.val:
prev.next = cur.next
nex = cur.next
cur.next = None
cur = nex

else:
prev = cur
cur = cur.next


return head