本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
83. 删除排序链表中的重复元素
本题来自 LeetCode：83. 删除排序链表中的重复元素[1]
题目描述
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1-1-2
输出: 1-2
示例 2:
输入: 1-1-2-3-3
输出: 1-2-3
解法一
题目分析
本题比较简单，采用双指针，一个指针用于迭代原链表，一个指针用于删除重复元素，记录不重复元素链表。
题目解答
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) {
return head;
}
// 记录无重复元素链表的尾节点
ListNode preNode = head;
// 迭代原链表的指针
ListNode curNode = head.next;
while(curNode != null) {
// 与无重复元素链表尾节点不相同，直接连接
if(curNode.val != preNode.val) {
preNode.next = curNode;
preNode = preNode.next;
}
curNode = curNode.next;
}
// 尾节点置null
preNode.next = null;
return head;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
解法二
题目分析
也可以直接在原链表上移除重复元素。
题目解答
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) {
return head;
}
ListNode curNode = head;
// 迭代原链表
while(curNode != null && curNode.next != null) {
// 删除重复元素
if(curNode.val == curNode.next.val) {
curNode.next = curNode.next.next;
} else {
curNode = curNode.next;
}
}
// 尾节点置null
curNode.next = null;
return head;
}
}
82. 删除排序链表中的重复元素 II
本题来自 LeetCode：82. 删除排序链表中的重复元素 II[2]
题目描述
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1-2-3-3-4-4-5
输出: 1-2-5
示例 2:
输入: 1-1-1-2-3
输出: 2-3
题目分析
和
83. 删除排序链表中的重复元素题不同的是，新链表需要将有重复的元素的元素全部去掉。可以采用双链表移除重复元素。
题目解答
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) {
return head;
}
// 无重复元素的新链表，头节点
ListNode dummy = new ListNode(-1);
// 无重复元素的新链表，尾节点
ListNode tailNode = dummy;
// 重复元素的开始节点
ListNode startNode = head;
// 迭代节点
ListNode curNode = head.next;
// 记录是否有和startNode相等的元素
boolean duplicated = false;
while(curNode != null) {
// 找到所有和startNode重复的节点
// 中止条件为curNode == null 或者curNode.val != startNode.val
while(curNode != null && curNode.val == startNode.val) {
curNode = curNode.next;
duplicated = true;
}
// 若startNode含有重复元素
if(duplicated) {
// 重置，直接移除掉以startNode开始的重复元素
duplicated = false;
} else {
// 若startNode只有一个，不包含重复元素，说明没有执行上面的while语句
// 将startNode连接到新链表中
tailNode.next = startNode;
tailNode = tailNode.next;
}
// 重置需要校验的元素设
startNode = curNode;
// 若curNode != null，进入下一个迭代
if(curNode != null) {
curNode = curNode.next;
}
// 若curNode = null，那么startNode = null
}
// 连接尾节点
tailNode.next = startNode;
return dummy.next;
}
}
复杂度分析：
时间复杂度：
O(n)
空间复杂度：
O(1)
参考资料
删除排序链表中的重复元素: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list
删除排序链表中的重复元素 II: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
原文始发于微信公众号（xiaogan的技术博客）：
