首页 > 代码库 > Remove Duplicates from Sorted List 去除链表中重复值节点
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.
如题目所诉，去除递增链表中重复值的节点。
刚开始思路如下：
- 设置一个指针用于遍历全部节点
- 让每个节点和其next节点值比较，若相同则将当前节点的next指向其next的next
- 继续遍历……
但是会有个问题，如果是{1,1,1}，那么遍历到第一个1的时候，判断和第二个1相同，则将第一个1的next指向第三个1.
程序结束，最后输出为{1,1}，所以此方法行不通。
基于上面的问题，需要设置一个临时指针来存放当前和其下个节点值重复的节点，因为根据题目要求，链表的值是递增的。
以{1,1,1,2,3,3}为例，首先将prev指针指向第一个1，（注：prev赋初值为节点head，当遇到有和其next值相同的节点时，再将此节点赋值为prev），判断并替换第二个1，将第一个1的next指向2，此时prev指向第一个1。
设置一个内层循环，判断后面的值是否和prev指向的1相同，当遇到第三个1时，因为他和1相同，所以，继续将第一个1指向第三个1的next，值为2，继续遍历……
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *deleteDuplicates(ListNode *head) {12 if(head == NULL)13 return head;14 15 ListNode *node = head;16 ListNode *prev = head;17 while(node->next != NULL){18 ListNode *cur_node = node->next;19 if(node->val == cur_node->val)20 if(cur_node->next != NULL){21 node->next = cur_node->next;22 prev = node;23 }else24 node->next = NULL;25 26 if(node->next != NULL)27 node = node->next;28 29 while(node->val == prev->val){30 if(node->next != NULL){31 prev->next = node->next;32 node = node->next;33 }else{34 prev->next = NULL;35 break;36 }37 38 }39 40 41 }42 43 return head;44 45 }46 };
Remove Duplicates from Sorted List 去除链表中重复值节点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。