题解 | #删除有序链表中重复的元素-II#

秒懂【删除链表元素】！超清晰图解一步步拆解。

1.思路

本题要求删除重复的元素即在链表中重复的元素都会被删除，由于重复的元素也有可能是头结点，因此需要定义一个链表的虚拟头结点，虚拟头结点的指针域指向链表的头结点。

假如链表结构如下图所示：

这时可以通过以下步骤完成链表重复元素的删除。

步骤一：定义虚拟头结点、指针变量。

cur ：链表节点衔接指针（当前操作的节点）；

nxt1：操作的下一个节点；

nxt2 ：操作的下下一个节点。

步骤二：循环删除链表的重复节点。

此时，nxt1与nxt2对应的节点值都是1（重复的元素），移动nxt2。

此时，nxt1与nxt2对应的节点值还是1（重复的元素），移动nxt2。

这时，nxt1的节点值是1，nxt2的值是2，需将已经检查出重复的元素1删除。删除重复元素1可以通过更改cur当前节点的指针域，让它指向nxt2，这样就可以将多个1节点删除。

之后再移动nxt1与nxt2，使得nxt1始终指向当前操作节点cur的下一个节点；nxt2始终指向当前操作节点cur的下下一个节点。

​ntx1 = cur.next # 下一个节点

​ ntx2 = cur.next.next # 下下一个节点

此时，nxt1与ntx2对应的节点值都是2（重复的元素），移动nxt2。

这时，nxt1的节点值是2，nxt2的值是3，需将已经检查出重复的元素2删除。删除重复元素2可以通过更改cur当前节点的指针域，让它指向nxt2，这样就可以将多个2节点删除。

之后再移动nxt1与nxt2，这时发现nxt1与nxt2中有一个为Null，循环退出（重复元素删除完成）。

步骤三：返回链表中无重复节点组成的链表头结点。

虚拟头节点的下一个节点就是需要返回的链表头节点，将其返回。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # write code here
        if head is None:
            return head

        # 1. 定义虚拟头结点、指针变量
        tmp_head = ListNode(-1)
        tmp_head.next = head
        cur = tmp_head  # 链表节点衔接指针（指向的是虚拟头结点，链表的第一个节点有可能与后面的值相同，存在删除链表第一个节点的情况）

        # 2. 循环删除链表的重复节点
        while cur.next is not None and cur.next.next is not None:
            ntx1 = cur.next  # 下一个节点
            ntx2 = cur.next.next  # 下下一个节点
            if ntx1.val == ntx2.val:
                # 下个节点的值 与 下下节点的值相同，需通过循环删除重复的元素（有可能出现连续重复的元素）
                val = ntx1.val
                while ntx2 is not None and ntx2.val == val:  # 循环比较的前提条件是：nxt2指针变量不为空
                    ntx2 = ntx2.next
                # 更改当前节点的指针域
                cur.next = ntx2
            else:
                # 移动当前节点指针变量
                cur = cur.next

        # 3.返回链表中无重复节点组成的链表头结点
        return tmp_head.next

2.2 Java代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        if (head == null) {
            return head;
        }
        // 1. 定义虚拟头结点、指针变量
        ListNode tmpHead = new ListNode(-1);
        tmpHead.next = head;
        ListNode cur =
            tmpHead;//链表节点衔接指针（指向的是虚拟头结点，链表的第一个节点有可能与后面的值相同，存在删除链表第一个节点的情况）

        // 2. 循环删除链表的重复节点
        while (cur.next != null && cur.next.next != null) {
            ListNode nxt1 = cur.next;  //下一个节点
            ListNode nxt2 = cur.next.next;  //下下一个节点
            if (nxt1.val == nxt2.val) {
                //下个节点的值 与 下下节点的值相同，需通过循环删除重复的元素（有可能出现连续重复的元素）
                int val = nxt1.val;
                while (nxt2 != null &&
                        nxt2.val == val) { //循环比较的前提条件是：nxt2指针变量不为空
                    nxt2 = nxt2.next;
                }
                //更改当前节点的指针域
                cur.next = nxt2;
            } else {
                //移动当前节点指针变量
                cur = cur.next;
            }
        }
        // 3.返回链表中无重复节点组成的链表头结点
        return tmpHead.next;
    }
}

2.3 Go代码

package main

import . "nc_tools"

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
func deleteDuplicates(head *ListNode) *ListNode {
	// write code here

	if head == nil {
		return nil
	}

	// 1. 定义虚拟头结点、指针变量
	tmpHead := &ListNode{Val: -1}
	tmpHead.Next = head
	cur := tmpHead //链表节点衔接指针（指向的是虚拟头结点，链表的第一个节点有可能与后面的值相同，存在删除链表第一个节点的情况）

	// 2. 循环删除链表的重复节点
	for cur.Next != nil && cur.Next.Next != nil {
		nxt1 := cur.Next
		nxt2 := cur.Next.Next
		if nxt1.Val == nxt2.Val {
			//下个节点的值 与 下下节点的值相同，需通过循环删除重复的元素（有可能出现连续重复的元素）
			val := nxt1.Val
			for nxt2 != nil && val == nxt2.Val { //循环比较的前提条件是：nxt2指针变量不为空
				nxt2 = nxt2.Next
			}
			cur.Next = nxt2 //更改当前节点的指针域

		} else {
			//移动当前节点指针变量
			cur = cur.Next

		}

	}
	// 3.返回链表中无重复节点组成的链表头结点
	return tmpHead.Next
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构