1. leetcode_21 - merge two ordered linked lists
Merge two ascending lists into a new ascending list and return. The new linked list is composed of all the nodes of the given two linked lists. Example 1: Input: l1 = [1,2,4], l2 = [1,3,4] Output:[1,1,2,3,4,4] Example 2: Input: l1 = [], l2 = [] Output:[] Example 3: Input: l1 = [], l2 = [0] Output:[0] Tips: The range of the number of nodes in the two linked lists is [0, 50] -100 <= Node.val <= 100 l1 and l2 They are arranged in non decreasing order https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
solution
create a new leading linked list to store the merged linked list. When merging two linked lists, compare the size of the node values of the two linked lists, and put those with smaller node values into the new linked list
finally, analyze whether the two linked lists have all put the elements into the new linked list. If not, put the nodes into the new linked list in turn, and finally return the next pointer of the new linked list
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { if (NULL == l1) return l2; if (NULL == l2) return l1; struct ListNode* pNew = (struct ListNode*)malloc(sizeof(struct ListNode)); pNew->next = NULL; struct ListNode* pNewL = pNew; // Tail node used to point to the new linked list // Insert the qualified nodes into the new linked list while (NULL != l1 && NULL != l2) { if (l1->val <= l2->val) { pNewL->next = l1; l1 = l1->next; } else { pNewL->next = l2; l2 = l2->next; } pNewL = pNewL->next; } // Put the remaining nodes into the new linked list in turn if (NULL != l1) { pNewL->next = l1; } else { pNewL->next = l2; } return pNew->next; }
2. leetcode_86. - separated list
Give you a list of the head node head And a specific value x ,Please separate the linked list so that all the items less than x All nodes appear in the x Before the node of. You should keep the initial relative position of each node in the two partitions. Example 1: Input: head = [1,4,3,2,5,2], x = 3 Output:[1,2,2,4,3,5] Example 2: Input: head = [2,1], x = 2 Output:[1,2] Tips: The number of nodes in the linked list is in the range [0, 200] within -100 <= Node.val <= 100 -200 <= x <= 200 leetcode: https://leetcode-cn.com/problems/partition-list/
solution
the requirement of the topic is to divide the linked list according to a certain value, so two leading linked lists can be constructed, which are divided into two cases. The nodes larger than val value and smaller than val value are respectively inserted into the two linked lists, and finally the two linked lists are merged, which is the desired linked list.
// Two leading linked lists are constructed, one is used to store nodes less than x, and the other is used to store nodes larger than x. the original size order will not be changed by tailing // Finally, merge the two linked lists struct ListNode* partition(struct ListNode* head, int x) { if (NULL == head || NULL == head->next) return head; struct ListNode lessL; lessL.next = NULL; struct ListNode moreL; moreL.next = NULL; struct ListNode* lessLL = &lessL; struct ListNode* moreLL = &moreL; // Constructing two new linked lists while (NULL != head) { if (head->val < x) { lessLL->next = head; lessLL = lessLL->next; } else { moreLL->next = head; moreLL = moreLL->next; } head = head->next; } // Splicing two linked lists lessLL->next = moreL.next; moreL.next = NULL; return lessL.next; }
3. leetcode_234 palindrome linked list
Please judge whether a linked list is palindrome linked list. Example 1: input: 1->2 output : false Example 2 : input : 1->2->2->1 output : true
solution
judge whether a linked list is a palindrome linked list. Because the palindrome linked list is symmetrical, the following method can be used.
- Looking for the middle node of the linked list
- The linked list after flipping the intermediate node
- Bit by bit comparison, if different nodes are found, it is not palindrome structure
// Flip linked list struct ListNode* reverseList(struct ListNode* head) { if (NULL == head || NULL == head->next) return head; struct ListNode* pPre = NULL; struct ListNode* pCur = head; struct ListNode* pNext = NULL; while (pCur != NULL) { pNext = pCur->next; pCur->next = pPre; pPre = pCur; pCur = pNext; } return pPre; } // Find the middle node of the linked list struct ListNode* middleNode(struct ListNode* head) { if (head == NULL) return NULL; struct ListNode* fast = head; struct ListNode* slow = head; // If the length of the linked list is even, then fast goes to the last part and the fast point is just NULL to stop the loop // If the length of the linked list is odd, then fast goes to the last step, and the current node is not empty. At that time, fast > next > next is empty, which will cause an error, so make sure that fast > next is not empty while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; } // The palindrome structure of the linked list is symmetric about the middle, so you can find the middle node of the linked list first // Reverse the back link list. Note whether there are different nodes between the reverse link list and the front link list. If so, it must not be palindrome structure bool isPalindrome(struct ListNode* head) { // The case that there is only one node in the linked list is absolutely palindrome structure if (NULL == head || NULL == head->next) return true; // If there are two nodes, judge whether the two nodes are the same, the same is palindrome structure if (head->next->next == NULL) { if (head->val == head->next->val) return true; else return false; } struct ListNode* pTmp = head; // Find the intermediate node struct ListNode* pMid = middleNode(head); // Split the linked list into two parts and reverse a part of the linked list at the same time struct ListNode* rear = pMid; pMid = NULL; // Reverse placement rear = reverseList(rear); // Comparison of inverted two part linked list while (NULL != rear && NULL != pTmp) { if (rear->val != pTmp->val) return false; rear = rear->next; pTmp = pTmp->next; } return true; }
4. leetcode_160 intersecting linked list
Write a program to find the starting node where two single linked lists intersect. Such as the following two linked lists: At node c1 Start to intersect. Example 1: Input: intersectVal = 8, listA = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input explanation: the value of the intersecting node is 8 (note that if two linked lists intersect, it cannot be 0). Starting from the respective header, the linked list A by[4, 1, 8, 4, 5],Linked list B by[5, 0, 1, 8, 4, 5]. stay A There are two nodes before the intersecting nodes; stay B In, there are three nodes before the intersecting node. Example 2: Input: intersectVal = 2, listA = [0, 9, 1, 2, 4], listB = [3, 2, 4], skipA = 3, skipB = 1 Output: Reference of the node with value = 2 Input explanation: the value of intersection node is 2 (note that if two linked lists intersect, it cannot be 0). Starting from the respective header, the linked list A by[0, 9, 1, 2, 4],Linked list B by[3, 2, 4]. stay A There are three nodes before the intersecting nodes; stay B In, there is one node before the intersecting node. Example 3: Input: intersectVal = 0, listA = [2, 6, 4], listB = [1, 5], skipA = 3, skipB = 2 Output: null Input explanation: calculate from the respective header, linked list A by[2, 6, 4],Linked list B by[1, 5]. Because the two linked lists do not intersect, so intersectVal Must be 0, and skipA and skipB It can be any value. Explanation: the two linked lists do not intersect, so return null.
solution
the intersection of two linked lists can be divided into three types: Y V L, because in the above structure, both linked lists intersect to a point, and the end nodes are the same after the intersection,
how to judge whether two linked lists intersect? We only need to detect whether the last node of two linked lists is the same. If they are the same, the linked lists must intersect
Thinking:
Determine whether two linked lists intersect
2. If it intersects, find the intersection point: calculate the length of two linked lists, let the longer linked list move the long short length first, and then the two linked lists move at the same time. If the two nodes have the same address, they intersect
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { if (NULL == headA || NULL == headB) return NULL; struct ListNode* pTmpA = headA; struct ListNode* pTmpB = headB; int lenA = 0; int lenB = 0; // 1. Judge whether two linked lists intersect while (pTmpA != NULL) { pTmpA = pTmpA->next; lenA++; } while (pTmpB != NULL) { pTmpB = pTmpB->next; lenB++; } if (pTmpA != pTmpB) return NULL; // 2. Find the intersection point // First calculate the length difference between two linked lists int distance = lenA - lenB; // Move one of the linked list pointers to the specified position pTmpA = headA; pTmpB = headB; if (distance < 0) { while (distance++ < 0) pTmpB = pTmpB->next; } else { while (distance-- > 0) pTmpA = pTmpA->next; } // Two pointers move at the same time to judge whether the address is the same while (pTmpA != NULL && pTmpB != NULL) { if (pTmpA == pTmpB) break; pTmpA = pTmpA->next; pTmpB = pTmpB->next; } return pTmpA; }