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

    删除链表重复元素

    题目描述

    思路分析 

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

    具体分析一下指针移动

     外部循环判定卡住的位置

    c语言代码：

    1. #include 
    2. #include 
    3.  
    4. struct ListNode
    5. {
    6.     int val;
    7.     struct ListNode *next;
    8. };
    9.  
    10. struct ListNode *deleteDuplicates(struct ListNode *head)
    11. {
    12.     // 把头结点做个备份的思想很好
    13.     if (!head)
    14.     {
    15.         return head;
    16.     }
    17.  
    18.     // 新建一个节点备份头结点,这也是一个哑结点
    19.     struct ListNode *dummy = (struct ListNode *)malloc(sizeof(struct ListNode));
    20.     dummy->next = head; // 下一个节点保存头结点，我们要让指针指向两比较结点最前面的一个结点
    21.  
    22.     struct ListNode *cur = dummy; // 让cur结点指向哑结点，cur结点改动，哑结点自然也会改动，最后要返回哑结点的next，也就是从头开始
    23.  
    24.     // 开始外部整体循环一次
    25.     // 内部相同数据多次循环
    26.     while (cur->next != NULL && cur->next->next != NULL)
    27.     {
    28.         // 如果遇到相同的节点，让内部指针移动
    29.         // 1  1  1 2  2 3
    30.         if (cur->next->val == cur->next->next->val)
    31.         {
    32.             int x = cur->next->val;
    33.             // 开始内部循环相同结点
    34.             while (cur->next != NULL && cur->next->val == x)
    35.             {
    36.                 cur->next = cur->next->next; // 1 1(指向这第一次) 1 2 2 3 //还会循环一次，指向 1 1 1 2(第二次，跳出内部) 2
    37.             }
    38.         }
    39.         else
    40.         {
    41.             // 如果不相等cur就正常往下面走，但是不改变next指向
    42.             cur = cur->next;
    43.         }
    44.     }
    45.  
    46.     // 整体循环完之后，返回dummy指向的next头结点
    47.     return dummy->next; // 返回头结点的地址
    48. }
    49.  
    50. void display(struct ListNode *head)
    51. {
    52.     while (head != NULL) 
    53.     {
    54.         printf("%d ", head->val);
    55.         head = head->next;
    56.     }
    57.     printf("\n---------\n");
    58. }
    59.  
    60. int main()
    61. {
    62.  
    63.     struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    64.     head->val = 1;
    65.     struct ListNode *p1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    66.     p1->val = 1;
    67.     struct ListNode *p2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    68.     p2->val = 2;
    69.     struct ListNode *p3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    70.     p3->val = 2;
    71.     struct ListNode *p4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    72.     p4->val = 3;
    73.     struct ListNode *p5 = (struct ListNode *)malloc(sizeof(struct ListNode));
    74.     p5->val = 4;
    75.     struct ListNode *p6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    76.     p6->val = 4;
    77.     
    78.     //把结点都连接起来
    79.     head->next = p1;
    80.     p1->next = p2;
    81.     p2->next = p3;
    82.     p3->next = p4;
    83.     p4->next = p5;
    84.     p5->next = p6;
    85.     p6->next = NULL;
    86.  
    87.     //打印节点
    88.     display(head);
    89.  
    90.     //删除重复结点
    91.     //头结点其实就是dummy结点的next结点
    92.     head = deleteDuplicates(head);
    93.  
    94.     display(head);
    95.  
    96.     return 0;
    97. }

    java代码实现：

    1. package com.pxx.leetcode.delDuplicates82;
    2.  
    3. //数据节点
    4. //直接用一个对象来做
    5. class ListNode {
    6.     int val;
    7.     ListNode next;
    8.  
    9.     public ListNode(int val, ListNode next) {
    10.         this.val = val;
    11.         this.next = next;
    12.     }
    13.  
    14.     public ListNode() {
    15.     }
    16.  
    17.     public ListNode(int val) {
    18.         this.val = val;
    19.     }
    20. }
    21.  
    22. class Solution {
    23.     public ListNode deleteDuplicates(ListNode head) {
    24.          if (head == null) {
    25.              return head;
    26.          }
    27.  
    28.          //哑结点
    29.         ListNode dummy = new ListNode(0, head);//哑结点的next指向头结点
    30.  
    31.         //移动结点
    32.         ListNode cur = dummy;//指针直接指向了哑结点
    33.  
    34.         //开始整体一次循环移动
    35.         while (cur.next != null && cur.next.next != null) {
    36.             //next与next.next是否相等
    37.             if (cur.next.val == cur.next.next.val) {
    38.                 //备份一个相等的节点值用于里布进行循环判定
    39.                 int x = cur.next.val;
    40.                 // （指针可以理解为先在头部） 1 1 1
    41.                 while (cur.next != null && cur.next.val == x) {
    42.                     //更改这片空间指向的next
    43.                     //如果头结点不一样，头结点也会改动
    44.                     cur.next = cur.next.next;//第一次 1 1（指向这个位置） 1
    45.                 }
    46.             } else {
    47.                 cur = cur.next;
    48.             }
    49.         }
    50.         return dummy.next;
    51.     }
    52. }
    53.  
    54.  
    55.  
    56. public class Solution1 {
    57.  
    58. }

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

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

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

    c语言代码实现：

    1. #include 
    2. #include 
    3.  
    4.  
    5. struct ListNode 
    6. {
    7.     int val;
    8.     struct ListNode *next;
    9. };
    10.  
    11. //目的：返回第一个不是重复数字的头
    12. //过程：递归控制有效指针的next移动
    13. struct ListNode* deleteDuplicates(struct ListNode* head) 
    14. {
    15.     //已经是最后一个结点
    16.     if (head == NULL || head->next == NULL)
    17.     {
    18.         return head;
    19.     }
    20.  
    21.     if (head->val != head->next->val)
    22.     {
    23.         //不相等直接改变next指向
    24.         head->next = deleteDuplicates(head->next);
    25.     }
    26.     else 
    27.     {
    28.         struct ListNode *move = head->next;
    29.         //把第一个有相同值节点的头当成头结点传入
    30.         while (move != NULL && move->val == head->val) 
    31.         {
    32.             //最后move移动到没有相同结点的位置
    33.             move = move->next;
    34.         }   
    35.  
    36.         return deleteDuplicates(move);//把不是相同的节点传进来
    37.     }
    38.  
    39.     //返回实际的next地址
    40.     //最后程序结束
    41.     return head;
    42. }
    43.  
    44. void display(struct ListNode *head)
    45. {
    46.     printf("\n-----\n");
    47.     while (head != NULL) 
    48.     {
    49.         printf("%d  %d\n", head->val, head->next);
    50.         head = head->next;
    51.     }
    52.     printf("\n---------\n");
    53. }
    54.  
    55.  
    56. int main()
    57. {
    58.     struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    59.     head->val = 1;
    60.     struct ListNode *p1 = (struct ListNode *)malloc(sizeof(struct ListNode));
    61.     p1->val = 3;
    62.     struct ListNode *p2 = (struct ListNode *)malloc(sizeof(struct ListNode));
    63.     p2->val = 3;
    64.     struct ListNode *p3 = (struct ListNode *)malloc(sizeof(struct ListNode));
    65.     p3->val = 5;
    66.     /*
    67.     struct ListNode *p4 = (struct ListNode *)malloc(sizeof(struct ListNode));
    68.     p4->val = 4;
    69.     struct ListNode *p5 = (struct ListNode *)malloc(sizeof(struct ListNode));
    70.     p5->val = 4;
    71.     struct ListNode *p6 = (struct ListNode*)malloc(sizeof(struct ListNode));
    72.     p6->val = 5;
    73.     */
    74.  
    75.     //把结点都连接起来
    76.     head->next = p1;
    77.     p1->next = p2;
    78.     p2->next = p3;
    79.     p3->next = NULL;
    80.  
    81.     display(head);
    82.  
    83.     head = deleteDuplicates(head);
    84.  
    85.     display(head);
    86.  
    87.  
    88.     return 0;
    89. }

    java代码实现

    1. package com.pxx.leetcode.delDuplicates82;
    2.  
    3. //数据节点
    4. //直接用一个对象来做
    5. class ListNode {
    6.     int val;
    7.     ListNode next;
    8.  
    9.     public ListNode(int val, ListNode next) {
    10.         this.val = val;
    11.         this.next = next;
    12.     }
    13.  
    14.     public ListNode() {
    15.     }
    16.  
    17.     public ListNode(int val) {
    18.         this.val = val;
    19.     }
    20. }
    21.  
    22. //采用一次遍历的方式来做
    23. class Solution {
    24.     public ListNode deleteDuplicates(ListNode head) {
    25.          if (head == null) {
    26.              return head;
    27.          }
    28.  
    29.          //哑结点
    30.         ListNode dummy = new ListNode(0, head);//哑结点的next指向头结点
    31.  
    32.         //移动结点
    33.         ListNode cur = dummy;//指针直接指向了哑结点
    34.  
    35.         //开始整体一次循环移动
    36.         while (cur.next != null && cur.next.next != null) {
    37.             //next与next.next是否相等
    38.             if (cur.next.val == cur.next.next.val) {
    39.                 //备份一个相等的节点值用于里布进行循环判定
    40.                 int x = cur.next.val;
    41.                 // （指针可以理解为先在头部） 1 1 1
    42.                 while (cur.next != null && cur.next.val == x) {
    43.                     //更改这片空间指向的next
    44.                     //如果头结点不一样，头结点也会改动
    45.                     cur.next = cur.next.next;//第一次 1 1（指向这个位置） 1
    46.                 }
    47.             } else {
    48.                 cur = cur.next;
    49.             }
    50.         }
    51.         return dummy.next;
    52.     }
    53. }
    54.  
    55.  
    56. //采用递归来做
    57. class Solution1 {
    58.     public ListNode deleteDuplicates(ListNode head) {
    59.         //最后一个结点就直接null,不做了
    60.         if (head == null || head.next == null) {
    61.             return head;
    62.         }
    63.  
    64.         if (head.val != head.next.val) {
    65.             //指针直接next往下面走动
    66.             head.next = deleteDuplicates(head.next);
    67.         } else {
    68.             ListNode move = head.next;
    69.             //移动到非相同数值的位置
    70.             while (move != null && move.val == head.val) {
    71.                 move = move.next;
    72.             }
    73.             return deleteDuplicates(move);//继续传入下一个值递归
    74.         }
    75.         return head;
    76.     }
    77. }
    78.  
    79. public class Lc1 {
    80.     public static void main(String[] args) {
    81.         ListNode head = new ListNode(1,null);
    82.         ListNode node1 = new ListNode(3,null);
    83.         ListNode node2 = new ListNode(3,null);
    84.         ListNode node3 = new ListNode(5,null);
    85.  
    86.         head.next = node1;
    87.         node1.next = node2;
    88.         node2.next = node3;
    89.         node3.next = null;
    90.  
    91.         //打印原始链表
    92.         display(head);
    93.  
    94.         //删除重复元素，调用递归的方法
    95.         Solution1 s1 = new Solution1();
    96.         head = s1.deleteDuplicates(head);
    97.         display(head);
    98.     }
    99.  
    100.     public static void display(ListNode head) {
    101.         while (head != null) {
    102.             System.out.print(head.val + " ");
    103.             head = head.next;
    104.         }
    105.         System.out.println();
    106.         System.out.println("-----");
    107.     }
    108.  
    109. }

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

  • 相关阅读:
    DPDK系列之三十一DPDK的并行机制简介
    淘宝/天猫API：item_search_neighbors-邻家好货
    【OpenCV入门学习--python】直方图的比较
    使用ping命令定位网络延迟问题
    五分钟教你如何制作学生期末网页作业(web前端期末大作业)
    ios版本小于13.4.1的手机需要前端对其调整图片方向，上传拍照照片总是方向不对
    asp.core 同时兼容JWT身份验证和Cookies 身份验证两种模式
    12.并发之ForkJoin框架详解
    声明式查询服务，只需定义，无需实现
    【Linux 系统】gcc/g++使用零星整理
  • 原文地址：https://blog.csdn.net/Pxx520Tangtian/article/details/134134699