剑指offer：合并两个有序的链表

文章目录

• • • 分析
    • 题目来源

分析

归并排序的思想：使用两个指针，分别指向两个链表，依次遍历两个链表，每次选择其中最小的插入到新链表中。

注意：这里新建一个虚拟节点dummy，第一个结点插入到dummy后面，最后返回的链表即为 dummy->next

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {auto dummy = new ListNode(-1); // 新建结点auto cur = dummy; // cur当前结点while(l1 && l2) { // 两个有序链表都不空if (l1->val <= l2->val) { // 第一个链表的节点值≤第二个链表的节点值cur->next = l1; cur = cur->next; // cur 后移指向l1l1 = l1->next; //l1后移，指向下一个结点}else { // 对称写法cur->next = l2;cur = cur->next;l2 = l2->next;}}if (l1) cur->next = l1; // 如果l1还不空直接挂过来else cur->next = l2; // l2挂过来return dummy->next; // 返回合并后链表的头节点} };

题目来源

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

总结

以上是生活随笔为你收集整理的剑指offer：合并两个有序的链表的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。