1. 第一个题目 合并两个有序链表
认真阅读题目
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
线索
递归实现
新链表 是有将两个有序链表合并成的
假设有方法mergeTwoLists能实现这样功能。
通过大小判断之后 继续这个方法
实现
- go
/**
描述：
1
Time complexity: O(n)
Space complexity: O(0)
**/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.Val < l2.Val {
l1.Next = mergeTwoLists(l1.Next, l2)
return l1
} else {
l2.Next = mergeTwoLists(l1, l2.Next)
return l2
}
}
- c++
class Solution {
public:
//Time complexity: O(n)
//Space complexity: O(0)
//Recursion
//输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
ListNode* 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;
}
}
};
2. 难度升级 第二个问题 合并K个排序链表
认真阅读题目
- 合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
关键：把每个链表看成一个元素，vector<元素>
分析
问题1. 这是k个 不是2个 感觉无从下手，转成成22合并
问题2. k个链表如何，通过什么方式知道 已经完成排序了呢。
步骤
1.如果是一个链表（从最简单开始） 就不需要合并 这就是结果
-
如果是多个 采用归并排序。对象就是n个链表。
什么情况适合递归？while？
代码
- c
//Time complexity: O(logn)
//Space complexity: O(0)
ListNode* mergeKLists(vector<ListNode*>& lists)
{
int n=lists.size();
if (n ==0)
{
return NULL;
}
return mergeLists(lists,0,n-1);
}
//
ListNode* mergeLists(vector<ListNode*>& lists,int begin,int end)
{
//递归推出条件,只有一个元素
if(begin == end)
{
return lists[begin];
}
int mid=(begin+end)/2;
ListNode* first=mergeLists(lists,begin,mid);
ListNode* second=mergeLists(lists,mid+1,end);
return mergeTwoLists(first,second);
}
ListNode* 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;
}
}
- go
func merge_K_Lists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
return sortmerge(lists, 0, len(lists)-1)
}
func sortmerge(lists []*ListNode, begin int, end int) *ListNode {
if begin >= end {
return lists[begin]
}
mid := (begin + end) / 2
p1 := sort_merge(lists, begin, mid)
p2 := sort_merge(lists, mid+1, end)
return mergeTwoLists(p1, p2)
}
第三个题目 148. 排序链表 难度有升级了
题目描述
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
分析
链表无法通过下标直接定位 听过其他方法都不很合适
采用归并排序，数组通过下标来分段处理的，
链表如何分段？ 指针特点出来了
代码
func sortList(head *ListNode) *ListNode {
//只有一个元素 归并排序推出条件
if head == nil || head.Next ==nil{
return head
}
fast := head
low := head
for fast!=nil &&fast.Next!=nil&&fast.Next.!=nil{
low=low.Next
fast=fast.Next.Next
}
//一个链表分割成2个链表
mid:=low.Next
low.Next=nil //非常重要
first := sortList(head)
second := sortList(mid)
return mergeTwoLists(first,second)
}
第四个题目 remove-duplicates-from-sorted-list-ii
- 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
题目理解
相同元素必须全部删除，如果比较相同元素，
需要2个变量，cur ，next
[1,1,1,1] 最后一个元素1和谁比较呢
code
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head ==NULL || head->next ==NULL)
{
return head;
}
int pre=head->val;
ListNode* temp;
if(head->val ==head->next->val)
{
while(head && pre ==head->val)
{
temp=head;
head=head->next;
temp->next=NULL;
delete temp;
}
return deleteDuplicates(head);
}else
{
head->next=deleteDuplicates(head->next);
return head;
}
}
};
remove-duplicates-from-sorted-list
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
分析
链表问题没有简单问题
method 1
循环遍历 比较当前元素和下个元素
如果相同 删除当前元素（删除下一个元素会有问题的）
继续遍历
最坏情况 全部相同 [1,1,1,1,1,1,1]
code
struct ListNode* deleteDuplicates(struct ListNode* head) {
if(head ==NULL ||head->next ==NULL)
{
return head; //只有一个元素
}
//compare
if(head->val ==head->next->val)
{
struct ListNode* temp=head;
head=head->next;
temp->next=NULL;
free(temp);
return deleteDuplicates(head);
}else
{
head->next=deleteDuplicates(head->next);
return head;
}
}
总结
- 递归结束条件是什么 一个数组，一个链表 ，一个tree
- 变化一步过程是什么
