Remove Duplicate from List(链表去重)
之前在一篇文章里总结了一部分链表的题目,这里主要例举一下链表去重的问题。链表去重有很多种情况,有些要求我们只保留单独出现的元素,有些要求我们使重复的元素只能出现一次。对于可能会删除头结点的题目,我们一般采用新建一个helper节点,使helper指向head,进行操作,最后返回helper.next就可以了。下面是leetcode中有关链表去重的一些题目
1,Remove Duplicates from Sorted List 给定一个链表,去除重复的元素,使每个元素最多出现一次。 例如:给定 1->1->2, 返回 1->2. 给定 1->1->2->3->3, 返回 1->2->3.
使用一个helper保留头结点,然后依次遍历链表。代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return null;
ListNode helper = head;
while(head.next != null) {
if(head.val == head.next.val) {
head.next = head.next.next;
} else {
head = head.next;
}
}
return helper;
}
}
2,Remove Duplicates from Sorted List II 给定一个链表,要求删除重复的元素,只保留单独的元素。 例如:给定 1->2->3->3->4->4->5, 返回 1->2->5. 给定 1->1->1->2->3, 返回 2->3.
因为头结点有可能被删除,此时我们用一个helper指向当前的头节点,进行遍历。代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) return head;
ListNode helper = new ListNode(0);
helper.next = head;
head = helper;
while(head.next != null && head.next.next != null) {
if(head.next.val == head.next.next.val){
int value = head.next.val;
while(head.next != null && head.next.val == value){
head.next = head.next.next;
}
} else {
head = head.next;
}
}
return helper.next;
}
}
3,Remove Linked List Elements 给定一个链表,一个目标元素target,删除链表中所有值为target的元素。 例如:给定: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, target = 6 返回: 1 --> 2 --> 3 --> 4 --> 5
我们分析这道题,因为头结点也可能被删除,所以我们的创建一个helper节点,指向head节点。代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode helper = new ListNode(0);
helper.next = head;
head = helper;
while(head.next != null) {
while(head.next != null && head.next.val == val) {
head.next = head.next.next;
}
if(head.next != null)
head = head.next;
else
break;
}
return helper.next;
}
}
链表总结这篇文章里介绍了在一个未排序的链表中删除节点,以及其它相似的问题,有兴趣的可以查看。