【剑指Offer】【链表】合并两个排序的链表

题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

A：若链表1为空，则合并后的链表头结点为pHead2；若链表2为空，则合并后的链表头结点为pHead1

　创建ret_Head作为合并链表的新头结点，比较pHead1和pHead2，ret_Head指向小的数，ret_Head->next指向两个链表中下一个最小的数 ====> 递归

A：同样的，递归也是一种栈结构，所以也可以用栈来解决这个问题

/*

struct ListNode {

	int val;

	struct ListNode *next;

	ListNode(int x) :

			val(x), next(NULL) {

	}

};*/

class Solution {

public:

    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)

    {

        if(pHead1 == nullptr)

        {

            return pHead2;

        }

        if(pHead2 == nullptr)

        {

            return pHead1;

        }

        ListNode *ret_Head = nullptr;

        if(pHead1->val < pHead2->val)

        {

            ret_Head = pHead1;

            ret_Head->next = Merge(pHead1->next,pHead2);

        }

        else

        {

            ret_Head = pHead2;

            ret_Head->next = Merge(pHead1,pHead2->next);

        }

        return ret_Head;

    }

};

相关题目：

　　每K个一组反转链表：给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　https://www.nowcoder.com/practice/a632ec91a4524773b8af8694a51109e7　　　　　　　　　　　　

　　　　　　　　　　　说明：

　　　　　　　　　　　　1. 你需要自行定义链表结构，将输入的数据保存到你的链表中；

　　　　　　　　　　　　2. 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换；

　　　　　　　　　　　　3. 你的算法只能使用常数的额外空间。

　　编程实现单链表的逆转函数：实现单链表的逆转函数，输入一个链表，反转链表后，返回翻转之后的链表。

　　LRU cache ：设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。

　　　　　　　　https://www.nowcoder.com/practice/3da4aeb1c76042f2bc70dbcb94513338

　　　　　　　 int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。

　　　　　　　　 void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。

　　　　　　　　请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。限制：请在O(1)的时间复杂度内完成上述2个操作。

巴特西

【剑指Offer】【链表】合并两个排序的链表

最新文章

热门文章