leetcode82删除排序链表中的重复元素

news/2025/2/22 19:13:45

删除链表重复元素

题目描述

思路分析 

思路1：采用一次遍历，内部循环判定是否相等

具体分析一下指针移动

 外部循环判定卡住的位置

c语言代码：

#include <stdio.h>
#include <stdlib.h>

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    // 把头结点做个备份的思想很好
    if (!head)
    {
        return head;
    }

    // 新建一个节点备份头结点,这也是一个哑结点
    struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    dummy->next = head; // 下一个节点保存头结点，我们要让指针指向两比较结点最前面的一个结点

    struct ListNode *cur = dummy; // 让cur结点指向哑结点，cur结点改动，哑结点自然也会改动，最后要返回哑结点的next，也就是从头开始

    // 开始外部整体循环一次
    // 内部相同数据多次循环
    while (cur->next != NULL && cur->next->next != NULL)
    {
        // 如果遇到相同的节点，让内部指针移动
        // 1  1  1 2  2 3
        if (cur->next->val == cur->next->next->val)
        {
            int x = cur->next->val;
            // 开始内部循环相同结点
            while (cur->next != NULL && cur->next->val == x)
            {
                cur->next = cur->next->next; // 1 1(指向这第一次) 1 2 2 3 //还会循环一次，指向 1 1 1 2(第二次，跳出内部) 2
            }
        }
        else
        {
            // 如果不相等cur就正常往下面走，但是不改变next指向
            cur = cur->next;
        }
    }

    // 整体循环完之后，返回dummy指向的next头结点
    return dummy->next; // 返回头结点的地址
}

void display(struct ListNode *head)
{
    while (head != NULL) 
    {
        printf("%d ", head->val);
        head = head->next;
    }
    printf("\n---------\n");
}

int main()
{

    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode *p1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p1->val = 1;
    struct ListNode *p2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p2->val = 2;
    struct ListNode *p3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p3->val = 2;
    struct ListNode *p4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p4->val = 3;
    struct ListNode *p5 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p5->val = 4;
    struct ListNode *p6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    p6->val = 4;
    
    //把结点都连接起来
    head->next = p1;
    p1->next = p2;
    p2->next = p3;
    p3->next = p4;
    p4->next = p5;
    p5->next = p6;
    p6->next = NULL;

    //打印节点
    display(head);

    //删除重复结点
    //头结点其实就是dummy结点的next结点
    head = deleteDuplicates(head);

    display(head);

    return 0;
}

java代码实现：

package com.pxx.leetcode.delDuplicates82;

//数据节点
//直接用一个对象来做
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         if (head == null) {
             return head;
         }

         //哑结点
        ListNode dummy = new ListNode(0, head);//哑结点的next指向头结点

        //移动结点
        ListNode cur = dummy;//指针直接指向了哑结点

        //开始整体一次循环移动
        while (cur.next != null && cur.next.next != null) {
            //next与next.next是否相等
            if (cur.next.val == cur.next.next.val) {
                //备份一个相等的节点值用于里布进行循环判定
                int x = cur.next.val;
                // （指针可以理解为先在头部） 1 1 1
                while (cur.next != null && cur.next.val == x) {
                    //更改这片空间指向的next
                    //如果头结点不一样，头结点也会改动
                    cur.next = cur.next.next;//第一次 1 1（指向这个位置） 1
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}



public class Solution1 {

}

思路2：采用递归的方式来做

上面就是如果头结点与它的next结点的值一样，那么就把这个头结点的next交给move结点，然后内部循环是否继续相等，知道不相等的时候跳出循环，继续以move为头结点进行递归，一旦到了一个与next不相等的位置，那么就把这个当前move指针的next继续下面递归，直到最后next等于NULL时候，停止递归，开始返回数据。

那么最早的头一定是最晚返回的数据，所以最后的head，一定就是头结点了。

c语言代码实现：

#include <stdio.h>
#include <stdlib.h>


struct ListNode 
{
    int val;
    struct ListNode *next;
};

//目的：返回第一个不是重复数字的头
//过程：递归控制有效指针的next移动
struct ListNode* deleteDuplicates(struct ListNode* head) 
{
    //已经是最后一个结点
    if (head == NULL || head->next == NULL)
    {
        return head;
    }

    if (head->val != head->next->val)
    {
        //不相等直接改变next指向
        head->next = deleteDuplicates(head->next);
    }
    else 
    {
        struct ListNode *move = head->next;
        //把第一个有相同值节点的头当成头结点传入
        while (move != NULL && move->val == head->val) 
        {
            //最后move移动到没有相同结点的位置
            move = move->next;
        }   

        return deleteDuplicates(move);//把不是相同的节点传进来
    }

    //返回实际的next地址
    //最后程序结束
    return head;
}

void display(struct ListNode *head)
{
    printf("\n-----\n");
    while (head != NULL) 
    {
        printf("%d  %d\n", head->val, head->next);
        head = head->next;
    }
    printf("\n---------\n");
}


int main()
{
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    head->val = 1;
    struct ListNode *p1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p1->val = 3;
    struct ListNode *p2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p2->val = 3;
    struct ListNode *p3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p3->val = 5;
    /*
    struct ListNode *p4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p4->val = 4;
    struct ListNode *p5 = (struct ListNode *)malloc(sizeof(struct ListNode));
    p5->val = 4;
    struct ListNode *p6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    p6->val = 5;
    */

    //把结点都连接起来
    head->next = p1;
    p1->next = p2;
    p2->next = p3;
    p3->next = NULL;

    display(head);

    head = deleteDuplicates(head);

    display(head);


    return 0;
}

java代码实现

package com.pxx.leetcode.delDuplicates82;

//数据节点
//直接用一个对象来做
class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    public ListNode() {
    }

    public ListNode(int val) {
        this.val = val;
    }
}

//采用一次遍历的方式来做
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         if (head == null) {
             return head;
         }

         //哑结点
        ListNode dummy = new ListNode(0, head);//哑结点的next指向头结点

        //移动结点
        ListNode cur = dummy;//指针直接指向了哑结点

        //开始整体一次循环移动
        while (cur.next != null && cur.next.next != null) {
            //next与next.next是否相等
            if (cur.next.val == cur.next.next.val) {
                //备份一个相等的节点值用于里布进行循环判定
                int x = cur.next.val;
                // （指针可以理解为先在头部） 1 1 1
                while (cur.next != null && cur.next.val == x) {
                    //更改这片空间指向的next
                    //如果头结点不一样，头结点也会改动
                    cur.next = cur.next.next;//第一次 1 1（指向这个位置） 1
                }
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}


//采用递归来做
class Solution1 {
    public ListNode deleteDuplicates(ListNode head) {
        //最后一个结点就直接null,不做了
        if (head == null || head.next == null) {
            return head;
        }

        if (head.val != head.next.val) {
            //指针直接next往下面走动
            head.next = deleteDuplicates(head.next);
        } else {
            ListNode move = head.next;
            //移动到非相同数值的位置
            while (move != null && move.val == head.val) {
                move = move.next;
            }
            return deleteDuplicates(move);//继续传入下一个值递归
        }
        return head;
    }
}

public class Lc1 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1,null);
        ListNode node1 = new ListNode(3,null);
        ListNode node2 = new ListNode(3,null);
        ListNode node3 = new ListNode(5,null);

        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        //打印原始链表
        display(head);

        //删除重复元素，调用递归的方法
        Solution1 s1 = new Solution1();
        head = s1.deleteDuplicates(head);
        display(head);
    }

    public static void display(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
        System.out.println("-----");
    }

}

好了，祝大家早安午安晚安


http://www.niftyadmin.cn/n/5140760.html

相关文章

如何开始开发一个跑腿App系统？

如何开始开发一个跑腿App系统？

1. 确定需求和功能规划 开始开发之前&#xff0c;需明确系统所需的基本功能&#xff0c;包括用户注册、登录、下单、配送员匹配、订单跟踪等。这些功能需要在系统设计之初明确。 2. 技术选型 选择适合的技术栈。前端可以使用框架如React、Vue.js&#xff0c;后端可选择Node…
阅读更多...
如何实现前端项目的自动化测试？一文4个步骤带你成功实现！

如何实现前端项目的自动化测试？一文4个步骤带你成功实现！

这其实就是我们常说的“UI自动化测试”&#xff0c;针对这个问题&#xff0c;我先告知答题思路如下&#xff1a; 1、什么是UI自动化&#xff1f;有什么优势&#xff1f; 2、UI自动化实践中会遇到什么难题&#xff1f; 3、如何解决难题&#xff0c;将UI落实到实践中&#xff1f;…
阅读更多...
Android8.1系统修改Chrome浏览器默认网址

Android8.1系统修改Chrome浏览器默认网址

项目中经常会遇到客户要求打开chrome浏览器默认进他们的官网&#xff0c;修改方法如下&#xff1a; 1. 在packages\providers\PartnerBookmarksProvider\src\com\android\providers\partnerbookmarks目录添加PartnerHomepageProviderExample.java文件&#xff0c;并修改文件中…
阅读更多...
NOIP2023模拟8联测29 集合

NOIP2023模拟8联测29 集合

题目大意 定义一个整数集合 S S S是好的&#xff0c;当且仅当 S S S中所有值域连续段的长度都不超过 k k k。 换句话说&#xff0c; S S S是好的&#xff0c;当且仅当不存在一对整数 l , r l,r l,r&#xff0c;满足 [ l , r ] [l,r] [l,r]中的整数都在 S S S中出现且 r − l …
阅读更多...
MATLAB野外观测站生态气象数据处理分析实践应用

MATLAB野外观测站生态气象数据处理分析实践应用

1.基于MATLAB语言 2.以实践案例为主&#xff0c;提供所有代码 3.原理与操作结合 4.布置作业&#xff0c;答疑与拓展 示意图&#xff1a; 以野外观测站高频时序生态气象数据为例&#xff0c;基于MATLAB开展上机操作&#xff1a; 1.不同生态气象要素文件的数据读写与批处理实现 …
阅读更多...
1597 - Searching the Web （UVA）

1597 - Searching the Web （UVA）

题目链接如下&#xff1a; Online Judge 我的代码如下&#xff1a; #include <iostream> #include <string> #include <vector> #include <cctype> #include <sstream> #include <map> #include <set> // #define debugstd::vect…
阅读更多...
Techlink TL24G06 网络变压器 10G 基座单端口变压器

Techlink TL24G06 网络变压器 10G 基座单端口变压器

功能特征&#xff1a; 1、符合IEEE 802.3标准。 2、符合RoHS。 3、工作温度范围&#xff1a;0C至70C。 4、储存温度范围&#xff1a;-20C至125C。
阅读更多...
thinkphp的自增setInc和自减setDec

thinkphp的自增setInc和自减setDec

// score 字段加 1 Db::table(think_user)->where(id, 1)->setInc(score); // score 字段加 5 Db::table(think_user)->where(id, 1)->setInc(score, 5); // score 字段减 1 Db::table(think_user)->where(id, 1)->setDec(score); // score 字段减 5 Db::tab…
阅读更多...
最新文章

Copyright @ 2022~2023