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

1、解题思路

1. 遍历链表：使用一个指针 curr 从链表头开始遍历。比较当前节点的值与其下一个节点的值： 如果相同，则跳过下一个节点（删除重复节点）。如果不同，则移动指针到下一个节点。
2. 终止条件：当 curr 或 curr.next 为 null 时停止遍历。

2、代码实现

C++

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        // write code here
        ListNode* cur = head;
        while (cur != nullptr && cur->next != nullptr) {
            if (cur->val == cur->next->val) {
                ListNode* tmp = cur->next;  // 保存重复节点
                cur->next = cur->next->next;// 跳过重复节点
                delete tmp;                 // 释放重复节点内存
            } else {
                cur = cur->next;            // 移动到下一个节点
            }
        }
        return head;
    }
};

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
        ListNode curr = head;
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                curr.next = curr.next.next;  // 跳过重复节点
            } else {
                curr = curr.next;            // 移动到下一个节点
            }
        }
        return head;
    }
}

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
        curr = head
        while curr and curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next  # 跳过重复节点
            else:
                curr = curr.next            # 移动到下一个节点
        return head

3、复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。