题目描述
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given1->2->3->3->4->4->5, return 1->2->5.
Given1->1->1->2->3, return 2->3.
- 思路
求去重后的链表头指针（重复的节点全部去掉）
从头结点开始遍历（用另一个变量保留头结点信息），当遍历到两节点不相等时，若该节点存在一次则连接，否则跳过遍历下一个节），注意开始节点可能被去掉。
可以采用计数法，对每个值相等的节点计数，当出现一次时就连接，这种方法避免出现重复节点判断复杂的问题。
或者采用递归，把当前方法看做返回第一个不重复节点的链表的头结点。当当前节点有重复时，找到第一个不与当前节点重复的节点放入该方法递归操作；当当前节点无重复时，定义当前节点的下一个节点为下一个节点放入该方法得到的头节点。最后返回该节点即可。最终的结果就是去重后的链表头指针。
//计数法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode pre = new ListNode(0);
ListNode Head = pre;
int cnt = 1;
while(head != null){
while(head.next != null && head.val == head.next.val){
head = head.next;
cnt ++;
}
if(cnt == 1){
pre.next = head;
pre = pre.next;
}else{
cnt = 1;
}
head = head.next;
}
pre.next = null;
return Head.next;
}
}
//递归
public class Solution {
public ListNode deleteDuplicates(ListNode head) { //返回第一个节点不重复的链表的头节点
if(head == null)
return null;
if(head.next != null && head.val == head.next.val){ //将与第一个节点重复的节点删除，并返回下一个节点
while(head.next != null && head.val == head.next.val){
head = head.next;
}
return deleteDuplicates(head.next);
}else{ // 定义当前节点（只出现了一次）的下一个节点
head.next = deleteDuplicates(head.next);
}
return head; //返回当前节点
}
}
