2016.5.57—— Remove Duplicates from Sorted List

Remove Duplicates from Sorted List

本题收获:

指针:

   不管什么指针在定义是就初始化:ListNode *head = NULL;

   如果给head指针赋值为第一个node节点数,则不需要开辟空间(的语句),直接:head = node; 如果另外赋值,需要开辟内存.  

   总之就是指针既要开辟内存(定义)又要赋值,只定义没有赋值的指针时野指针,危害很大。

    指针在删除不用时,删除后,需要让指针指向NULL。    delete p_t;
                                       p_t = NULL;

  题目: 

  Given a sorted linked list, delete all duplicates such that each element appear only once.

  For example,
  Given 1->1->2, return 1->2.
  Given 1->1->2->3->3, return 1->2->3.

  思路:

  我的思路:遍历,看是否相同。

  leetcode/dicuss的思路:注意题目说了是已排序的,那么就看现在的节点和下一个节点是否相同,相同的话删除(指向NULL),让下一个指向下下一个,cur->next = cur ->next ->next;

  代码:

 1 ListNode* deleteDuplicates_SimpleOneByOne_16ms(ListNode* head)
 2 {
 3     ListNode* node  = head;
 4     while(node && node->next)
 5     {
 6         if(node->val == node->next->val)
 7         {
 8             delete node->next;
 9             node->next = node->next->next;
10         }
11         else
12             node = node->next;
13     }
14
15     return head;
16 }

  代码2:测试的main函数在链表的输入输出中有 

 1 public class Solution {
 2     public ListNode deleteDuplicates(ListNode head) {
 3         if (head == null) return head;
 4
 5         ListNode cur = head;
 6         while(cur.next != null) {
 7             if (cur.val == cur.next.val) {
 8                 cur.next = cur.next.next;
 9             }
10             else cur = cur.next;
11         }
12         return head;
13     }
14 }

  2的main函数

 1 int main()
 2 {
 3     ListNode head(0), node1(1), node2(3),node3(3);            //对每一个节点赋值
 4     head.next = &node1;        //head.next是指向的地址, node是值
 5     node1.next = &node2;
 6     node2.next = &node3;
 7     node3.next = NULL;
 8     while (head.next != NULL)
 9     {
10         //cout << head.val << endl;
11         //if (head.next == NULL)
12         //{
13         //    cout << "aa" << endl;        //测试是否为空指针
14         //    break;
15         //}
16         cout << head.val <<‘ ‘;
17         head = *(head.next);            //这里要注意
18     }
19     cout << endl;
20     system("pause");
21     return 0;
22 }

  代码1的测试mian函数:

  1 #include "stdafx.h"
  2 #include "iostream"
  3 #include "vector"
  4 #include "malloc.h"
  5 using namespace std;
  6
  7 struct Listnode
  8 {
  9     int val;
 10     Listnode *next;
 11     Listnode(int x) :val(x), next(NULL){};
 12 };
 13
 14 class MyClass
 15 {
 16 public:
 17     Listnode *removeDuplicate(Listnode *head)
 18     {
 19         //cout << head->val << endl;
 20         if (head == NULL) return head;
 21             //cout << head->val<< endl;
 22         Listnode *cur;
 23         cur = head->next;
 24         if (cur->next->next == NULL)
 25             cout << ‘b‘ << endl;
 26         while (cur->next != NULL)
 27         {
 28             //cout << ‘c‘<< endl;
 29
 30             if (cur->val == cur->next->val)
 31             {
 32                 Listnode *p_t = cur->next;        //释放删除元素的内存,用了new如果要删除的话,最好释放内存
 33                 cur->next = cur->next->next;
 34                 delete p_t;
 35                 p_t = NULL;                        //不加的话很容易为垂直指针,容易内存泄漏
 36                 //cout << cur->val << endl;
 37             }
 38             else
 39                 cur = cur->next;
 40             //cout << cur->val << endl;
 41         }
 42         //cout << head->val << endl;
 43         return head;
 44         //cout << head->val << endl;
 45     }
 46
 47 };
 48
 49 //方法1:单个链表节点赋值,可以运行,但是给head1单独开辟空间,会显示空间值(why,怎么不显示)
 50
 51 int _tmain(int argc, _TCHAR* argv[])
 52 {
 53     //指针在定义时就初始化
 54     Listnode *head1 = NULL, *node1 = NULL, *node2 = NULL, *node3 = NULL, *node4 = NULL, *head2 = NULL;        //这里粗心,应该是分号写成逗号,提示错误1.error C2040: “node1”:“Listnode”与“Listnode *”的间接寻址级别不同 2.
 55
 56     //head1 = new Listnode();                        //提示错误2:error C2440: “初始化”: 无法从“Listnode *”转换为“Listnode”    无构造函数可以接受源类型,或构造函数重载决策不明确
 57     head1 = (Listnode *)malloc(sizeof(Listnode));    //分配内存的方法
 58     head1 = 0;
 59     //head1 = (Listnode *)malloc(2);
 60
 61     node1 = new Listnode(1);
 62     node2 = new Listnode(2);
 63     node3 = new Listnode(2);
 64     node4 = new Listnode(4);
 65
 66     //head1 = node1;                //这种方法给head1指针地址最好??
 67     head1->next = node1;
 68     node1->next = node2;
 69     node2->next = node3;
 70     node3->next = node4;
 71     node4->next = NULL;
 72
 73
 74     MyClass solution;
 75     head2 = solution.removeDuplicate(head1);
 76     while(head2 != NULL)                    //输出不是for是while
 77     {
 78         cout << head2->val <<‘ ‘;
 79         head2 = head2->next;
 80     }
 81     cout << endl;
 82     system("pause");
 83     return 0;
 84 }
 85 /*
 86 //方法2:数组赋值给链表节点,这种方法OK
 87 int main()
 88 {
 89     Listnode *head1 = NULL, *node1 = NULL, *node2 = NULL, *head2 = NULL;
 90     vector<int> nums = { 1, 1, 2, 4, 6, 6 };
 91     for (size_t i = 1; i < nums.size(); i++)
 92     {
 93         node1 = new Listnode(nums.at(i));
 94         if (head1 == NULL)
 95         {
 96             head1 = node1;
 97         }
 98         else node2->next = node1;            //这两句注意注意
 99         node2 = node1;                        //在这里node2和head1并没有联系????,node2是一个指针,不是数值,注意!!!!
100     }
101
102     MyClass solution;
103     head2 = solution.removeDuplicate(head1);
104     while (head2 != NULL)                    //输出不是for是while
105     {
106         cout << head2->val << ‘ ‘;
107         head2 = head2->next;
108     }
109     cout << endl;
110     system("pause");
111     return 0;
112
113 }
114
115 //方法3:数组赋值,首先给head开辟空间,不能运行(why)                                        //这种提前给head1开辟空间的为什么不可以????
116 int main()
117 {
118     Listnode *head1 = NULL, *node1 = NULL, *node2 = NULL, *head2 = NULL;
119
120     vector<int> nums = { 1, 1, 2, 4, 6, 6 };
121     head1 = (Listnode *)malloc(sizeof(Listnode));
122     //node2 = new Listnode(nums.at(0));
123     //head1 = node2;
124     for (size_t i = 1; i < nums.size(); i++)
125     {
126         node1 = new Listnode(nums.at(i));
127         node2->next = node1;                        //将node2看做一个指针cur
128         node2 = node1;
129     }
130
131     MyClass solution;
132     head2 = solution.removeDuplicate(head1);
133     while (head2 != NULL)                    //输出不是for是while
134     {
135         cout << head2->val << ‘ ‘;
136         head2 = head2->next;
137     }
138     cout << endl;
139     system("pause");
140     return 0;
141 }*/

  在测试过程中出现错误:

    1.error C2040: “node1”:“Listnode”与“Listnode *”的间接寻址级别不同

    2.error C2440: “初始化”: 无法从“Listnode *”转换为“Listnode”    无构造函数可以接受源类型,或构造函数重载决策不明确

  这两个错误的原因是L54处将分号“;”,错写成逗号“,”,系统认为定义没有定义完,将下面一行误认为是Listnode的定义。

    还有出现如下:

    

    是因为出现空指针,这就需要检查指针的定义以及初始化,删除,删除后指向NULL,等一系列指针的操作。

      使用指针时一定注意,指针定义,初始化,赋值。

时间: 05-28

2016.5.57—— Remove Duplicates from Sorted List的相关文章

2016.6.17——Remove Duplicates from Sorted Array

Remove Duplicates from Sorted Array 本题收获: 1.“删除”数组中元素 2.数组输出 题目: Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this i

【LeetCode】Remove Duplicates from Sorted Array 解题报告

[LeetCode]Remove Duplicates from Sorted Array 解题报告 标签(空格分隔): LeetCode [LeetCode] https://leetcode.com/problems/remove-duplicates-from-sorted-array/ Total Accepted: 129010 Total Submissions: 384622 Difficulty: Easy Question Given a sorted array, remov

leetCode 26. Remove Duplicates from Sorted Array 数组

26. Remove Duplicates from Sorted Array Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant mem

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice? For example, Given sorted array nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn'

Leetcode | Remove Duplicates from Sorted Array I &amp;&amp; II

Remove Duplicates from Sorted Array I Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memor

26. Remove Duplicates from Sorted Array【easy】

26. Remove Duplicates from Sorted Array[easy] Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with consta

26. Remove Duplicates from Sorted Array【leetcode】,数组,array,java,算法

26. Remove Duplicates from Sorted Array Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant mem

Leetcode-83 Remove Duplicates from Sorted List

#83. Remove Duplicates from Sorted List Given a sorted linked list, delete all duplicates such that each element appear only once. For example, Given 1->1->2, return 1->2. Given 1->1->2->3->3, return 1->2->3. /** * Definition fo

LeetCode(82): Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II:Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. For example,Given 1->2->3->3->4->4->5, return 1->2->5.Given 1->