Article directory

 remove list element
 Merge two sorted linked lists
 reverse linked list
 middle node of linked list
 The kth node from the bottom in the linked list
 Linked list split
 Palindromic linked list
 Intersecting linked list
 circular linked list
 Ring List II π±
 Copy linked list with random pointer π°
 Summarize
remove [list] element
Give you the head node of a linked list
head
and an integerval
, please delete allNode.val == val
the , and return the new head node
Idea 1 : A more common way to find differences while traversing. We can define two pointers, one pointing to the head node and one set to NULL. When encountering the same value, skip directly. point to the next bit. At the same time, we have to pay attention to the problem of head deletion, because the function given in the title has the head node head.
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur = head; struct ListNode*prev = NULL; while(cur) { if(cur>val == val) { if(cur==head) { head = head>next; free(cur); cur = head; } else { prev>next = cur>next; free(cur); cur = prev>next; } } else { prev = cur; cur = cur>next; } } return head; }
Idea 2 : Give a new linked list, not the end of the val node can be inserted into the new linked list. The last node is set to NULL. At the same time, we still need to pay attention to the problem of the head node
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur = head; struct ListNode*newhead= NULL,*tail =NULL; while(cur) { if(cur>val!=val) { if(tail==NULL) { newhead = tail = cur; } else { tail>next = cur; tail = tail>next; } cur = cur>next; } else { struct ListNode*del = cur; cur = cur>next; free(del); } } if(tail) tail>next = NULL; return newhead; }
It is not difficult for us to find that if there is no head node, we have to pay attention, so we can give a singly linked list of the head node to implement :
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode*cur = head; struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode*tail = guard; while(cur) { if(cur>val != val) { tail>next = cur; tail = tail>next; cur = cur>next; } else { struct ListNode*del = cur; cur = cur>next; free(del); } } if(tail) tail>next = NULL; head = guard>next; free(guard); return head; }
After we have the head node, we don’t need to think about deleting the first element.
Merge two sorted linked lists
Merge two ascending linked lists into a new ascending linked list and return. The new linked list is formed by splicing all the nodes of the given two linked lists.
Idea: It is relatively simple, create a linked list with a head node, compare the size of the data, and insert the tail after the new linked list.
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode*guard = (struct ListNode*)malloc(sizeof(struct ListNode)); guard>next = NULL; struct ListNode*cur1 = list1; struct ListNode*cur2 = list2; struct ListNode*tail = guard; while(cur1&&cur2) { if(cur1>val<cur2>val) { tail>next = cur1; cur1 = cur1>next; } else { tail>next = cur2; cur2 = cur2>next; } tail = tail>next; } if(cur1) { tail>next = cur1; } if(cur2) { tail>next = cur2; } struct ListNode*head = guard>next; free(guard); return head; }
reverse linked list
Given the head node of the singly linked list
head
, please reverse the linked list and return the reversed linked list.
Idea 1: Take the node and insert it into a new node
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur = head; struct ListNode*newhead = NULL; while(cur) { struct ListNode*next = cur>next; cur>next = newhead; newhead = add; cur = next; } return newhead; }
Idea 2: Flip the direction of the pointer directly to flip the linked list
struct ListNode* reverseList(struct ListNode* head){ struct ListNode*cur = head; struct ListNode*prev = NULL; while(cur) { struct ListNode*next = cur>next; cur>next = prev; prev = cur; cur = next; } return prev; }
middle node of linked list
Given
head
a , return the middle node of the linked list.If there are two intermediate nodes, return the second intermediate node.
Idea: You can traverse it once to find the length divided by 2. However, we can use another method to just traverse the linked list once, using the fast and slow pointers. The slow pointer takes one step at a time, and the fast pointer takes two steps at a time. We need to distinguish whether it is an odd number of nodes or an even number of nodes.
For odd numbers: fast to the end, and slow to just the middle node
For even numbers: fast goes to empty, while slow just goes to the middle node.
struct ListNode* middleNode(struct ListNode* head){ struct ListNode*fast = head; struct ListNode*slow = head; while(fast&&fast>next) { slow = slow>next; fast = fast>next>next; } return slow; }
The kth node from the bottom in the linked list
Input a linked list and output the kth node from the bottom of the linked list.
Idea: still use the fast and slow pointer approach. Slow takes one step at a time, while fast we let it take K steps first . Then go at the same time.
struct ListNode* FindKthToTail (struct ListNode* pListHead, int k ) { // write code here struct ListNode * slow = pListHead ,* fast = pListHead ; while (k){ //k is greater than the length of the linked list if (fast == NULL ) return NULL ; fast = fast>next; } while(fast){ fast = fast>next; slow = slow>next; } return slow; }
fast What if you take the K1 step first? What about changing K to βK? We need to modify some of the conditions inside (we focus on analyzing some boundary problems):
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { // write code here struct ListNode*slow = pListHead,*fast = pListHead; while(fast&&k){ fast = fast>next; } if(fast == NULL) return NULL; while(fast>next){ fast = fast>next; slow = slow>next; } return slow; }
Linked list split
There is a head pointer ListNode pHead* of a linked list , given a certain value x, write a piece of code to arrange all nodes less than x before the rest of the nodes, and the original data order cannot be changed, and return the head pointer of the rearranged linked list.
Idea: We give two new linked lists with head nodes, the value less than X is placed in the first linked list, the value greater than X is placed in the second linked list, and the last two new linked lists can be connected. At the same time, we need to note that if the linked list is empty, we can draw a picture:
public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode*lessguard = (ListNode*)malloc(sizeof(ListNode)); lessguard>next = NULL; ListNode*lesstail = lessguard; ListNode*greaterguard = (ListNode*)malloc(sizeof(ListNode)); greaterguard>next =NULL; ListNode*greatertail = greaterguard; ListNode*cur = pHead; while(cur) { if(cur>val<x) { lesstail>next = cur; lesstail = lesstail>next; } else { greatertail>next = cur; greatertail = greatertail>next; } cur = cur>next; } lesstail>next = greaterguard>next; greatertail>next = NULL; pHead = lessguard>next; free(lessguard); free(greaterguard); return pHead; } };
Palindromic linked list
Given the head node of a singly linked list
head
, please judge whether the linked list is a palindrome linked list. If yes, returntrue
; otherwise, returnfalse
.
Idea: Find the middle position, invert the second half, and compare, and it will be NULL at the end. This is actually a collection of finding the intermediate node of the linked list and reversing the linked list :
class Solution { public: struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* cur = head; while (cur) { struct ListNode* next = cur>next; cur>next = newhead; newhead = add; cur = next; } return newhead; } struct ListNode* middleNode(struct ListNode* head) { struct ListNode*slow = head; struct ListNode*fast = head; while(fast&&fast>next) { slow = slow>next; fast = fast>next>next; } return slow; } bool isPalindrome (ListNode* head) { // write code here struct ListNode * mid = middleNode ( head ); struct ListNode * ret = reverseList ( mid ); //1 2 3 2 1 // reverse middle first // 1 2 1 2 3 while (head && ret) { if (head>val == ret>val) { head = head>next; ret = ret>next; } else { return false ; } } return true; } };
Another solution: create a linked list to store the inversion result of the original linked list, and then compare it with the original linked list one by one to determine whether it is a palindrome :
class Solution { public: bool isPalindrome(ListNode* head) { // write code here struct ListNode*cur = head; struct ListNode*newhead = NULL; struct ListNode*next = NULL; while(cur) { newhead = (struct ListNode*)malloc(sizeof(struct ListNode)); newhead>val = cur>val; newhead>next = next; next = newhead; cur = cur>next; } while(head) { if(newhead>val!=head>val) { return false ; } else { newhead =newhead>next; head = head>next; } } return true; } };
Intersecting linked list
Given the head nodes headA and headB of two singly linked lists, please find and return the starting node where the two singly linked lists intersect. Returns null if the two linked lists do not have intersecting nodes.
The illustration shows that the two linked lists intersect at node c1:
The title data guarantees that there are no cycles in the entire chain structure.
Idea: First of all, it is necessary to determine whether there is any intersection, whether the addresses of the end nodes are the same
Find the intersection point – find the length, which is the length of LenA and LenB. The long linked list takes the difference step first, and then walks at the same time. The first equality is the required intersection, because we have already judged whether it intersects.
struct ListNode * getIntersectionNode (struct ListNode *headA, struct ListNode *headB) { struct ListNode * curA = headA ,* curB = headB ; int LenA = 0 ; int LenB = 0 ; while (curA) { curA = curA>next; LenA++; } while(curB) { curB = curB>next; LenB++; } if(curA!=curB) { return NULL; } struct ListNode*longList = headA,*shortList = headB; if(LenA<LenB) { longList = headB; shortList = headA; } int gap = abs(LenALenB); while(gap) { longList = longList>next; } while(longList != shortList) { longList = longList>next; shortList = shortList>next; } return longList; }
circular linked list
Give you the head node of a linked list, and determine whether there is a cycle in the linked list.
If there is a node in the linked list that can be reached again by continuously tracing the next pointer, there is a cycle in the linked list. To represent a cycle in a given linked list, the evaluation system internally uses the integer pos to represent the position in the linked list where the tail of the linked list is connected (index starts from 0). Note: pos is not passed as a parameter. Just to identify what the linked list actually is.
Returns true if there is a cycle in the linked list. Otherwise, return false.
Idea: A linked list with a ring cannot be traversed. . . We can use fast and slow pointers to solve this problem. Fast and slow pointers, that is, slow pointers take one step at a time, fast pointers take two steps at a time, and the two pointers start to run from the actual position of the linked list. If the linked watch has a ring, it will definitely meet in the ring. Otherwise the fast pointer goes to the end of the linked list first :
bool hasCycle(struct ListNode *head) { struct ListNode*slow = head; struct ListNode*fast = head; while(fast &&fast>next) { slow = slow>next; fast = fast>next>next; if(slow == fast) { return true; } } return false ; }
extension problem
Why does the fast pointer take two steps at a time, and the slow pointer can catch up with one step, will I miss it?

Slow take one step at a time, fast take three steps at a timeβ

Slow takes one step at a time, fast takes X steps at a timeβ

slow takes Y steps at a time, fast takes X steps at a timeβ
The latter problem is also a similar solution. What about taking one step at a time for slow and X steps at a time for fast? Each time the distance is reduced by X1
And what about slow taking Y steps at a time and fast taking X steps at a time? Each time the distance is reduced by XY
This is actually a matter of relative distance reduction.
Ring List II π±
Given the head node head of a linked list, return the first node that the linked list starts to enter the ring. Returns null if the linked list has no cycle.
If there is a node in the linked list that can be reached again by continuously tracing the next pointer, there is a cycle in the linked list. To represent a cycle in a given linked list, the evaluation system internally uses the integer pos to represent the position in the linked list where the tail of the linked list is connected (index starts from 0). If pos is 1, there are no cycles in the list. Note: pos is not passed as a parameter, just to identify the actual situation of the linked list.
Modifying the linked list is not allowed.
Idea 1: Here is a conclusion (the first node in the ring):
Let a pointer start traversing the linked list from the starting position of the linked list, and at the same time let a pointer start to run around the circle from the position of the meeting point, both pointers take one step each time, and will eventually meet at the position of the entry point .
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode*slow = head,*fast = head; while(fast && fast>next) { slow = slow>next; fast = fast>next>next; if(slow == fast) { struct ListNode*meet = slow; while(head!=meet) { head = head>next; meet = meet>next; } return meet; } } return NULL; }
Idea 2: Convert into an intersecting linked list. After disconnecting from the meeting point, as a linked list, the other linked list starts from the beginning. The first node of the linked list to enter the ring is equivalent to the intersection of these two linked lists, and finding the intersection of the linked lists is The above topics intersect the linked list.
struct ListNode * getIntersectionNode (struct ListNode *headA, struct ListNode *headB) { struct ListNode * curA = headA ,* curB = headB ; int LenA = 0 , LenB = 0 ; while (curA) { curA = curA>next; LenA++; } while(curB) { curB = curB>next; LenB++; } if(curA != curB) { return NULL ; } struct ListNode*longlist = headA,*shortlist = headB; if(LenA<LenB) { longlist = headB; shortlist = headA; } int gap = abs(LenALenB); while(gap) { longlist = longlist>next; } while(longlist!=shortlist) { longlist = longlist>next; shortlist = shortlist>next; } return longlist; } struct ListNode *detectCycle(struct ListNode *head) { struct ListNode*slow = head,*fast = head; while(fast && fast>next) { slow = slow>next; fast = fast>next>next; if(slow == fast) { //find the meeting point struct ListNode * meet = slow ; struct ListNode * next = meet > next ; // disconnect meet>next = NULL ; struct ListNode * enterNode = getIntersectionNode ( head , next ); // restore the original linked list meet>next = next; return enterNode; } } return NULL; }
Copy linked list with random pointer π°
You are given a linked list of length n, each node contains an additional random pointer random, which can point to any node in the linked list or an empty node.
Constructs a deep copy of this linked list. A deep copy should consist of exactly n new nodes, where the value of each new node is set to the value of its corresponding original node. The next pointer and random pointer of the new node should also point to the new node in the copied linked list, so that these pointers in the original linked list and the copied linked list can represent the same linked list state. None of the pointers in the copied linked list should point to the nodes in the original linked list.
For example, if there are two nodes X and Y in the original linked list, where X.random –> Y . Then the corresponding two nodes x and y in the replication linked list also have x.random –> y .
Returns the head node of the replicated linked list.
A linked list in input/output is represented by a linked list consisting of n nodes. Each node is represented by a [val, random_index]:
val: An integer representing Node.val.
random_index: The index of the node pointed to by the random pointer (ranging from 0 to n1); null if it does not point to any node.
Your code only accepts the head node of the original linked list as an incoming parameter.
This question is more difficult. If we replicate each node, the randomness of this problem is more difficult for us to deal with:
struct Node* copyRandomList(struct Node* head) { struct Node* cur = head; struct Node*copy = NULL; struct Node*next = NULL; while(cur) { //assign link next = cur>next; copy = (struct Node*)malloc(sizeof(struct Node)); copy>val = cur>val; cur>next = copy; copy>next = next; cur = next; } //Update the random of copy cur = head; while(cur) { copy = cur>next; if(cur>random == NULL) { copy>random = NULL; } else { copy>random = cur>random>next; } //iterate cur = cur>next>next; } //copy nodes are unlinked and linked together to restore the original linked list struct Node*copyHead = NULL ,*copyTail = NULL ; cur = head; while(cur) { copy = cur>next; next = copy>next; / / Take the node tail insertion if (copyTail == NULL ) { copyHead = copyTail = copy; } else { copyTail>next = copy; copyTail = copyTail>next; } // restore the original list cur>next = next; cur = next; } return copyHead; }
Summarize
Through the above linked list OJ questions, we have a deeper understanding of linked lists, and at the same time, we have learned some problemsolving methods. At the same time, for the questions, the first thing we need to do is to understand the meaning of the questions, and then we need to draw more pictures. It is convenient for us to better deal with some details.
Of course, there are still many OJ questions for linked lists. The questions here are just the representative of linked list questions. It does not mean that this is the question of all linked lists.