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

1.思路

本题是：删除有序链表中重复的元素，即重复的元素需要保留一个，同时限定了链表是有序的（这样只需要比较相邻的元素值）。

这时可以通过一个操作指针变量cur就可以完成题目的要求。

假如有序链表如下图所示：

alt

步骤一：定义操作节点指针变量。

alt

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

  • 当前节点与下个节点值相同，删除下一个节点

    cur对应的节点值1与它的下一个节点值1相同，则删除下一个节点（更改cur的指针域： cur.next = cur.next.next）。之后再将cur移动到下一个节点（2节点）便于后序的操作。

alt

  • 节点值不相同，移动指针变量cur

    cur指向节点2与下一个节点值3不相同，则将cur移动到一个节点（3节点）。

alt

如果cur对应的下一个节点为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. 定义操作节点指针变量
        cur = head

        # 2.  循环删除链表重复节点
        while cur.next is not None:
            if cur.val == cur.next.val:
                # 2.1 当前节点与下个节点值相同，删除下一个节点
                cur.next = cur.next.next
            else:
                # 2.2 节点值不相同，才移动指针变量
                cur = cur.next
        # 3. 返回头结点
        return head

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 cur = head;

        // 2. 循环删除链表重复节点
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                // 2.1当前节点与下个节点值相同，删除下一个节点
                cur.next = cur.next.next;
            } else {
                // 2.2 节点值不相同，才移动指针变量
                cur = cur.next;
            }
        }

        // 3. 返回头结点
        return head;
    }
}

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 head
	}
	// 1. 定义操作节点指针变量
	cur := head

	// 2. 循环删除链表重复节点
	for cur.Next != nil {
		if cur.Val == cur.Next.Val {
			// 2.1当前节点与下个节点值相同，删除下一个节点
			cur.Next = cur.Next.Next
		} else {
			// 2.2 节点值不相同，才移动指针变量
			cur = cur.Next
		}
	}
	// 3. 返回头结点
	return head
}

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