21. 合并两个有序链表
image.png
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/*
wrong
if (l1 && l2) {
if (l1->val == l2->val) {
L1last = l1;
L2last = l2;
l1 = l1->next;
l2 = l2->next;
L1last->next = L2last;
} else if (l1->val > l2->val) {
} else {
}
if (l1 && l2) {
if (l1->val <= l2val) {
L1last = l1;
l1 = l1->next;
L1last->next = l2;
} else {
L2last = l2;
l2 = l2->next;
L2last->next = l1;
}
} else if (l1) {
*/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
if (l1 == NULL) {
return l2;
}
if (l2 == NULL) {
return l1;
}
//需要一个pre 指针
struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode)); // 需要malloc
struct ListNode* head = pre;
while (l1!=NULL && l2!=NULL) {
// if (l1== NULL && l2 == NULL) {
// break;
// }
// if (l1 == NULL) {
// pre->next = l2;
// break;
// }
// if (l2 == NULL) {
// pre->next = l1;
// break;
// }
if (l1->val <= l2->val) {
pre->next = l1;
l1 = l1->next;
} else {
pre->next = l2;
l2 = l2->next;
}
pre = pre->next;
}
pre->next = (l1 == NULL) ? l2 : l1;
return head->next;
}
61. 旋转链表 （快慢指针）
-
相关标签 : 链表 双指针
image.png
思路：
K=1 的话 就是 倒数第二个节点指向空， 最后一个节点变成新的头节点
K= N 就是重复K=1 的操作 N次
K是可以优化的
找倒数第二个节点
struct ListNode* getEnd(struct ListNode* head)
{
struct ListNode* end = head;
while (end->next && end->next->next) {
end = end->next;
}
return end;
}
实现代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/*
find 找伟大 一个一个踢出去
会超时 12 / 231
[1,2,3]
2000000000
优化
1. K优化
*/
int getLen(struct ListNode* head)
{
int l = 0;
while (head) {
head = head->next;
l++;
}
return l;
}
struct ListNode* getEnd(struct ListNode* head)
{
struct ListNode* end = head;
while (end->next && end->next->next) {
end = end->next;
}
return end;
}
struct ListNode* rotateRight(struct ListNode* head, int k){
if (head == NULL || head->next == NULL) {
return head;
}
k = k % getLen(head);
struct ListNode* end;
struct ListNode* newHead;
while (k) {
end = getEnd(head);
// printf("end %d", end->val);
newHead = end->next;
end->next = NULL;
newHead->next = head;
head = newHead;
// printf(" | head %d\n", head->val);
k--;
}
return head;
}
148. 排序链表 （快慢指针 + merge sort）
image.png
思路：
看到nlogn 想到快排和归并
快排 没法再 链表做 swap() 排除
选择归并 divide - merge
merge 两个链表 21.合并两个有序链表
divide 链表 需要使用快慢指针
// mid -> linked list -> fast slow ptr
struct ListNode* getMid(struct ListNode* head)
{
// struct ListNode *fast = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *fast = head;
struct ListNode *slow = fast;
while (fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
printf("slow %d - \n", slow->val);
return slow;
}
实现代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/*
nlogn - > quick sort , divide and merge, heap sort
*/
// mid -> linked list -> fast slow ptr
struct ListNode* getMid(struct ListNode* head)
{
// struct ListNode *fast = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode *fast = head;
struct ListNode *slow = fast;
while (fast->next != NULL && fast->next->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
printf("slow %d - \n", slow->val);
return slow;
}
// merge -> pre
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* pre = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* head = pre;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
pre->next = l1;
l1 = l1->next;
} else {
pre->next = l2;
l2 = l2->next;
}
pre = pre->next;
}
pre->next = (l1 == NULL) ? l2 : l1;
return head->next;
}
// divide
struct ListNode* sortList(struct ListNode* head){
if (head == NULL || head->next == NULL) { // remain one element
return head;
}
struct ListNode* mid = getMid(head);
struct ListNode* right = mid->next;
mid->next = NULL; // divide
struct ListNode* left = sortList(head);
right = sortList(right);
return merge(left, right);
}
109. 有序链表转换二叉搜索树
image.png
- 相关标签： DFS 链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/*
二分 + 递归
*/
struct ListNode* getMid(struct ListNode* head)
{
struct ListNode *fast = head;
struct ListNode *slow = fast;
int flag = 0;
while (fast->next && fast->next->next) {
fast = fast->next->next;
if (flag == 0) {
flag = 1;
continue;
}
slow = slow->next;
}
return slow;
}
struct TreeNode* sortedListToBST(struct ListNode* head){
if (head == NULL) {
return NULL;
}
struct TreeNode *tree = (struct TreeNode *)malloc(sizeof(struct TreeNode));
memset(tree, 0, sizeof(struct TreeNode));
if (head->next == NULL) {
tree->val = head->val;
return tree;
}
struct ListNode *mid = getMid(head);
tree->val = mid->next->val;
struct ListNode *right = mid->next->next;
mid->next->next = NULL;
mid->next = NULL;
tree->left = sortedListToBST(head);
tree->right = sortedListToBST(right);
return tree;
}
网友评论