题目描述
Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given1->1->2, return1->2.
Given1->1->2->3->3, return1->2->3.
题目大意
给定一个有序链表,删除其中重复元素,仅剩下一个。
如例子所见。
第一种方法
思路
维护两个指针,前指针负责向后遍历,后指针负责连接不重复的元素。
注意delete操作,以防止内存泄漏。
代码
#include<iostream>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
typedef ListNode* list_node; // 别名
ListNode *deleteDuplicates(ListNode *head)
{
if(head == NULL)return NULL;
list_node p1 = head;
list_node p2 = head->next;
while(p2)
{
// 值相等
if(p1->val == p2->val)
{
p1->next = NULL; // 暂且先把p1的next置为NULL
list_node tmp = p2; // 暂存p2
p2 = p2->next; // p2指针后移
delete tmp;
}
else
{
p1->next = p2;
p1 = p1->next;
p2 = p2->next;
}
}
return head;
}
int main()
{
list_node p1, p2, p3, p4, p5;
p1 = new ListNode(1);
p2 = new ListNode(1);
p3 = new ListNode(2);
p4 = new ListNode(3);
p5 = new ListNode(3);
p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p5;
p1 = deleteDuplicates(p1);
while(p1)
{
cout << p1->val << ' ';
p1 = p1->next;
}
return 0;
}
运行结果
第二种方法
思路
思路跟第一种并无大的区别。
代码
typedef ListNode* list_node; // 别名
ListNode *deleteDuplicates(ListNode *head)
{
if(head == NULL)return head;
list_node cur = head;
while(cur != NULL)
{
while(cur->next != NULL && cur->val == cur->next->val)
{
list_node tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
cur = cur->next;
}
return head;
}
运行结果
以上。
网友评论