从零开始算法之路 ----有序链表去重

缺乏、安全感 2022-01-31 18:29 242阅读 0赞

前言：小白入门题解，算法大佬可以直接跳过此博客（大佬轻喷哈）

题源：leetcode（[https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/][https_leetcode-cn.com_problems_remove-duplicates-from-sorted-list]）

题目描述：

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:

输入: 1->1->2
    输出: 1->2

示例 2:

输入: 1->1->2->3->3
    输出: 1->2->3

**解决方案一：**递归套路

解题思路：

1.  找终止条件：当head指向链表为空或只剩一个元素的时候，自然是不可能重复的，因此return
2.  返回什么值：应该返回的自然是已经去重的链表的头节点
3.  每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head

核心代码：

//去重函数 
    ListNode* Solution::deleteDuplicates(ListNode *head){
    	//如果链表为空或者只有一个有元素链表肯定不会重复 
    	if(head == NULL || head->next == NULL)
    	    return head;
    	head->next = deleteDuplicates(head->next);
    	if(head->val == head->next->val) head = head->next;
    	return head;  
    }

完整代码：

#include<iostream>
    using namespace std;
    
    struct ListNode {
         int val;
         ListNode *next;
         //用参数初始化表对数据成员初始化 
         ListNode(int x=0) : val(x), next(NULL) {}
      };
     
    class Solution {
    	ListNode *head;
    
    public:
    	Solution(){
    		head = new ListNode;
    	} 
    	//去重函数 
        ListNode* deleteDuplicates(ListNode* head) ;
        //输入函数 
    	void input();
    	//输出 链表函数
    	void output(); 
    	//获得头节点
    	ListNode* getHead(){
    		return head;
    	} 
    };
    
    //输入函数 初始化链表
    void Solution::input(){
    	ListNode *pre,  *newNode;
    	pre = head;
    	int  val;
    	printf("请逐个输入链表:");
    	while(scanf("%d", &val)){
    		// 如果val 等于100 输入结束（100 为约定的结束标准） 
    		if(val == 100) break; 
    		//初始化新节点 
    		newNode = new ListNode(val);
    		// 把新节点连接着当前节点 pre 之后 
    		pre->next = newNode;
    		// 把新节点变为当前节点 
    		pre = newNode; 		
    	}	
    } 
    
    // 输出链表函数
    void Solution::output(){
    	ListNode *current = head->next;
    	while(current != NULL){
    		printf("%d ", current->val);
    		current = current->next; 
    	}
    	printf("\n输出链表结束!");	
    } 
    
    //去重函数 
    ListNode* Solution::deleteDuplicates(ListNode *head){
    	//如果链表为空或者只有一个有元素链表肯定不会重复 
    	if(head == NULL || head->next == NULL)
    	    return head;
    	head->next = deleteDuplicates(head->next);
    	if(head->val == head->next->val) head = head->next;
    	return head;  
    }
    
    int main(){
    	Solution s1;
    	s1.input();
    	s1.deleteDuplicates(s1.getHead()); 
    	s1.output();
    	return 0;
    	
    }

**解决方案二：**非递归

解题思路：

1.定义两个变量（first,second）,first指向第一个节点，second 指向第二个节点，  
    2.比较first指向节点的值和second指向节点的值，  
    3.如果这两个值相等（如果不相等，使first指向该节点，重复2），则second指向下一个节点，  
       直到找到和first指向节点不相等的节点，使first指向该节点，重复上述步骤2、3，直到链表最后一个节点 ，返回去重链表头结点

核心代码：

//去重函数 
    ListNode* Solution::deleteDuplicates(ListNode *head){
        
        //当链表为空或者只有一个元素的时候自然是不会重复的 
        if(head == NULL || head->next == NULL) 
    	    return head;
    	//定义两个变量（first,second）,first指向第一个节点，second 指向第二个节点， 
    	ListNode *first, *second;
    	first = head;
    	second = first->next;
    	// first 指向的节点不为空 
    	while(first != NULL){
    		// second 指向的节点不为空并且 first指向节点的值和second指向节点的值
    		while(second!= NULL && first->val == second->val){
    			//如果这两个值相等，则second指向下一个节点
    			second = second->next;
    		}
    		//使first指向的下一个节点指向second指向的节点
    		first->next = second;
    		// 使first指向的节点指向 second指向的节点
    		first = second;
    	} 
    	return head;
    }

完整代码：

#include<iostream>
    using namespace std;
    
    struct ListNode {
         int val;
         ListNode *next;
         //用参数初始化表对数据成员初始化 
         ListNode(int x=0) : val(x), next(NULL) {}
      };
     
    class Solution {
    	ListNode *head;
    
    public:
    	Solution(){
    		head = new ListNode;
    	} 
    	//去重函数 
        ListNode* deleteDuplicates(ListNode* head) ;
        //输入函数 
    	void input();
    	//输出 链表函数
    	void output(); 
    	//获得头节点
    	ListNode* getHead(){
    		return head;
    	} 
    };
    
    //输入函数 初始化链表
    void Solution::input(){
    	ListNode *pre,  *newNode;
    	pre = head;
    	int  val;
    	printf("请逐个输入链表:");
    	while(scanf("%d", &val)){
    		// 如果val 等于100 输入结束（100 为约定的结束标准） 
    		if(val == 100) break; 
    		//初始化新节点 
    		newNode = new ListNode(val);
    		// 把新节点连接着当前节点 pre 之后 
    		pre->next = newNode;
    		// 把新节点变为当前节点 
    		pre = newNode; 		
    	}	
    } 
    
    // 输出链表函数
    void Solution::output(){
    	ListNode *current = head->next;
    	while(current != NULL){
    		printf("%d ", current->val);
    		current = current->next; 
    	}
    	printf("\n输出链表结束!");	
    } 
    
    //去重函数 
    ListNode* Solution::deleteDuplicates(ListNode *head){
        
        //当链表为空或者只有一个元素的时候自然是不会重复的 
        if(head == NULL || head->next == NULL) 
    	    return head;
    	//定义两个变量（first,second）,first指向第一个节点，second 指向第二个节点， 
    	ListNode *first, *second;
    	first = head;
    	second = first->next;
    	// first 指向的节点不为空 
    	while(first != NULL){
    		// second 指向的节点不为空并且 first指向节点的值和second指向节点的值
    		while(second!= NULL && first->val == second->val){
    			//如果这两个值相等，则second指向下一个节点
    			second = second->next;
    		}
    		//使first指向的下一个节点指向second指向的节点
    		first->next = second;
    		// 使first指向的节点指向 second指向的节点
    		first = second;
    	} 
    	return head;
    }
    int main(){
    	Solution s1;
    	s1.input();
    	s1.deleteDuplicates(s1.getHead()); 
    	s1.output();
    	return 0;
    	
    }

[https_leetcode-cn.com_problems_remove-duplicates-from-sorted-list]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/