力扣83. 删除排序链表中的重复元素（java常规解法 + 建立虚拟头节点）

Problem: 83. 删除排序链表中的重复元素

思路

常规解法：一次遍历，每次判断若当前节点值和其下一个节点值，若相等则当前节点指向其下一个节点的下一个节点。
建立虚拟头节点和尾指针（准确来说应该是一种技巧）：建立虚拟头节点和尾指针，遍历时当当前指向的节点值和尾指针指向的节点值不同时将其添加到尾指针上。

解题方法

常规解法:

1.循环退出条件为cur != null && cur.next != null(cur为开始定义指向链表头节点并且用于遍历链表的辅助指针)；
2.每次判断若当前节点值和其下一个节点值，若相等则当前节点指向其下一个节点的下一个节点；否则直接迭代（cur = cur.next）

建立虚拟头节点和尾指针:

1.建立虚拟头节点，辅助遍历指针指向链表头，尾指针指向建立的虚拟头节点（该操作能够较好的解决原始待删除链表头部就存在重复值的情况）
2.循环退出条件为辅助遍历指针不为空。
3.若辅助遍历指针当前指向的节点值和尾指针指向的节点值不相同，则让尾指针指向该节点，否则正常迭代遍历（实际操作细节看代码）
4.返回虚拟头节点的下一个节点

复杂度

常规解法:

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

建立虚拟头节点和尾指针:

• 时间复杂度:

$O(n)$

• 空间复杂度:

$O(1)$

Code

常规解法:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //Time Complexity: O(n)
    //Space Complexity: O(1)
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode cur = head;
        //当当前节点和其下一个节点均不为null
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

建立虚拟头节点和尾指针:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //Time Complexity: O(n)
    //Space Complexity: O(1)
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        //建立虚拟头节点
        ListNode dummyNode = new ListNode(-666);
        dummyNode.next = head;
        //建立头指针和尾指针
        ListNode p = head;
        //尾指针指向虚拟头节点
        ListNode tail = dummyNode;
        while (p != null) {
            //先将下一个节点取出
            ListNode nextNode = p.next;
            if (p.val != tail.val) {
                tail.next = p;
                tail = p;
                tail.next = null;
            }
            p = nextNode;
        }
        return dummyNode.next;
    }
        
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37