首页 > 代码库 > LeetCode——Remove Duplicates from Sorted List II

LeetCode——Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

原题链接:https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

题目:给定一个已排序的链表,删除重复的元素,只留下源链表中唯一出现的那些元素。

思路:首先防止把头节点删除,构建一个虚拟的头节点。由于是已排序的,相等的元素就在相邻的位置上,发现有相邻的元素,则指针依次向后指,直到没有相等的相邻元素为止。

	public ListNode deleteDuplicates(ListNode head) {
		if (head == null || head.next == null)
			return head;

		ListNode dummy = new ListNode(0);
		dummy.next = head;
		head = dummy;

		while (head.next != null && head.next.next != null) {
			if (head.next.val == head.next.next.val) {
				int val = head.next.val;
				while (head.next != null && head.next.val == val) {
					head.next = head.next.next;
				}
			} else {
				head = head.next;
			}
		}

		return dummy.next;
	}

	// Definition for singly-linked list.
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}