LeetCode Remove Duplicates from Sorted List & Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List

Description:

Given a sorted linked list, delete all duplicates such that each element appear only once.

Solution:

每次while循環，都判斷目前節點與下一個節點的val是否一樣，一樣則改變目前節點的next指針，否則跳到下一個節點。

import java.util.*;

public class Solution {
	public ListNode deleteDuplicates(ListNode head) {
		ListNode temp = head;
		ListNode next;
		while (temp != null) {
			next = temp.next;
			if (next == null)
				break;
			if (temp.val == next.val) {
				temp.next = next.next;
			} else {
				temp = next;
			}
		}
		return head;
	}
}
           

Remove Duplicates from Sorted List II

  Description:

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

Solution:

利用two pointer方法，每次對于當下要周遊的節點t1，都用進行另外一次周遊，記為t2，一直搜尋到null或者t1和t2的val不同。如果t2是t1的next，那麼就表示t1沒有重複值，否則t1指派到t2，繼續周遊。

import java.util.*;

public class Solution {
	public ListNode deleteDuplicates(ListNode head) {
		ListNode t1, t2;

		t1 = head;
		t2 = head;
		while (t1 != null) {
			t2 = t1;
			while (t2 != null) {
				if (t2.val != t1.val)
					break;
				t2 = t2.next;
			}
			if (t1.next == t2) {
				break;
			} else {
				t1 = t2;
			}
		}

		head = t1;
		t1 = t2 = head;
		ListNode temp = head;
		while (t1 != null) {
			t2 = t1;
			while (t2 != null) {
				if (t2.val != t1.val)
					break;
				t2 = t2.next;
			}
			if (t1.next == t2) {
				temp.next = t1;
				temp = temp.next;
				System.out.println(temp.val);
				t1.next = null;
				t1 = t2;
			} else {
				t1 = t2;
			}
		}

		return head;
	}
}