从零开始算法之路 ----合并两个有序链表

ゞ浴缸里的玫瑰 2022-01-30 15:49 178阅读 0赞

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

题源：leetcode（[https://leetcode-cn.com/problems/merge-two-sorted-lists/][https_leetcode-cn.com_problems_merge-two-sorted-lists]）

题目描述：

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

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

//合并两个有序链表 
    ListNode* Solution::mergeTwoLists(ListNode *l1, ListNode *l2){
    	 if(l1 == NULL) return l2;
    	 if(l2 == NULL) return l1;
    	 if(l1->val < l2->val){
    	 	l1->next = mergeTwoLists(l1->next,l2);
    	 	return l1;
    	 } else{
    	 	l2->next = mergeTwoLists(l1,l2->next);
    	 	return l2;
    	 }
    }

完整代码：

#include<iostream>
    using namespace std;
    
    struct ListNode {
         int val;
         ListNode *next;
         //用参数初始化表对数据成员初始化 
         ListNode(int x=0) : val(x), next(NULL) {}
      };
     
    class Solution {
    	ListNode *first;
    
    public:
    	Solution(){
    		first = new ListNode;
    	} 
    	//去重函数 
        ListNode* deleteDuplicates(ListNode* head) ;
        //输入函数 
    	void input();
    	//输出 链表函数
    	void output(); 
    	//获得头节点
    	ListNode* getHead(){
    		return first;
    	} 
    	//合并两个有序链表
    	ListNode * mergeTwoLists(ListNode *L1, ListNode *L2); 
    };
    
    //输入函数 初始化链表
    void Solution::input(){
    	ListNode *pre,  *newNode;
    	pre = first;
    	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 = first->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;
    
    //   if(head == NULL || head->val != head->val)
    //       return head;
        
        //当链表为空或者只有一个元素的时候自然是不会重复的 
        if(head == NULL || head->next == NULL) 
    	    return head;
    		
    	//思路：1.定义两个变量（first,second）,first指向第一个节点，second 指向第二个节点，
    	//      2.比较first指向节点的值和second指向节点的值，
        //      3.如果这两个值相等（如果不相等，使first指向该节点，重复2），则second指向下一个节点，
    	//        直到找到和first指向节点不相等的节点，使first指向该节点，重复上述步骤2、3，直到
    	//      链表最后一个节点 
    	//定义两个变量（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;
    }
    
    //合并两个有序链表 
    ListNode* Solution::mergeTwoLists(ListNode *l1, ListNode *l2){
    	 if(l1 == NULL) return l2;
    	 if(l2 == NULL) return l1;
    	 if(l1->val < l2->val){
    	 	l1->next = mergeTwoLists(l1->next,l2);
    	 	return l1;
    	 } else{
    	 	l2->next = mergeTwoLists(l1,l2->next);
    	 	return l2;
    	 }
    }
    
    int main(){
    	Solution s1,s2;
    	s1.input();
    	s2.input();
    	s1.mergeTwoLists(s1.getHead(), s2.getHead());
    	s1.output();
    
    	return 0;
    	
    }

[https_leetcode-cn.com_problems_merge-two-sorted-lists]: https://leetcode-cn.com/problems/merge-two-sorted-lists/