Leetcode 83 Remove Duplicates from Sorted List
【摘要】
题意描述
Given a sorted linked list, delete all duplicates such that each element appear only once.
Exam...
题意描述
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;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
但是这样其实会有个小问题，也就是重复数据节点只是跳过了，并没有释放相应的内存。
这时候就需要用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;
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
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
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
文章来源: blog.csdn.net，作者：herosunly，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/herosunly/article/details/87542820
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）