[LintCode] Remove Duplicates form Sorted List I & II
文章目录
Remove Duplicates form Sorted List I
Problem
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Note
遇到后一个结点和当前结点相等,就用当前结点指向下一个的下一个结点。
Solution
public class Solution {
public static ListNode deleteDuplicates(ListNode head) {
if (head == null) return head;
ListNode node = head;
while (node.next != null) {
if (node.val == node.next.val) node.next = node.next.next;
else node = node.next;
}
return head;
}
}
Remove Duplicates form Sorted List II
Problem
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
Note
和上一道题不同的地方就是,需要用双指针操作,且最后要返回dummy.next,以防止head结点即duplicate的情况返回错误的结果。
令pre = dummy, cur = head,用cur进行查重操作,pre是cur的前结点。当cur和cur.next等值的时候,cur后移至第一个不等值的点,用pre指向新的cur即可。
Solution
public class Solution {
public static ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy, cur = head;
while (cur != null && cur.next != null) {
if (cur.val == cur.next.val) {
int val = cur.val;
while (cur != null && cur.val == val) cur = cur.next;
pre.next = cur;
}
else {
pre = pre.next;
cur = cur.next;
}
}
return dummy.next;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论