263.LeetCode | 21. 合并两个有序链表

vlambda
2021-03-23

263.LeetCode | 21. 合并两个有序链表

每天一个开发小知识

题目

将两个升序链表合并为一个新的升序链表并返回

新链表是通过拼接给定的两个链表的所有节点组成的

思路

通过双指针同时遍历两个链表

为处理头结点为空的情况

引入哨兵节点

即在头结点之前再加一个节点

解法：双指针 + 哨兵

时间复杂度 O(n)，空间复杂度 O(1)

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode * dummy = new ListNode(); ListNode * p = dummy; ListNode * q = l1; ListNode * f = l2; while (NULL != q || NULL != f) { if (NULL != q && NULL != f) { if (q->val < f->val) { p->next = q; p = p->next; q = q->next; } else { p->next = f; p = p->next; f = f->next; } } else if (NULL != q) { p->next = q; p = p->next; q = q->next; } else { p->next = f; p = p->next; f = f->next; } }
 return dummy->next; }};