leetcode|leetcode 链表 [C语言] leetcode链表[C语言]

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. 旋转链表（快慢指针） 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; }

【leetcode|leetcode 链表 [C语言]】实现代码

/** * 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） 148. 排序链表

文章图片
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. 有序链表转换二叉搜索树 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; }