Linked list of linear list OJ (Part 2)
"I don't sing loud love songs, it doesn't mean there's no moment of heartbreak" -- lonely patients
Previous linked list OJ (I) [previous linked list OJ (I)]( https://blog.csdn.net/m0_60965347/article/details/124068805?spm=1001.2014.3001.5501 )The
I believe we are all ready to welcome the slightly more difficult linked list OJ, rush!
1. Linked list segmentation (Niuke)
Title Link: [CM11 linked list segmentation]( Linked list segmentation_ Niuke Tiba_ Niuke (nowcoder.com))
Title Description:
There is a header pointer 1ListNode* pHead of a linked list. Given a certain value of X, write a piece of code to rank all nodes less than x before other nodes, and the original data order cannot be changed. Return the header pointer of the rearranged linked list.
Idea: similar to the idea of merging two ordered linked lists in the previous period, this time we will use two linked lists. In order to simplify our logic, we will use the linked list with sentry.
- Traverse the original linked list, one node with a storage value less than x, and the other node with a storage value greater than or equal to X.
- Connect the two linked lists
- Record the head to return and release the sentry
Illustration:
Code implementation:
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
ListNode* LessHead=new ListNode(0);
ListNode* GreaterHead=new ListNode(0);
ListNode *LessTail=LessHead, *GreaterTail=GreaterHead;
for(ListNode* cur=pHead;cur;cur=cur->next)
{
if(cur->val<x)
{
LessTail->next=cur;
LessTail=cur;
}
else
{
GreaterTail->next=cur;
GreaterTail=cur;
}
}
LessTail->next=GreaterHead->next;
GreaterTail->next=NULL;
ListNode* head=LessHead->next;
delete LessHead;
delete GreaterHead;
return head;
}
};
2. Palindrome structure of linked list
Title Link: [palindrome structure of linked list]( Palindrome structure of linked list_ Niuke Tiba_ Niuke (nowcoder.com))
Title Description:
For a linked list, please design an algorithm with time complexity of O(n) and additional space complexity of O(1) to judge whether it is palindrome structure.
Given the header pointer A of A linked list, please return A bool value to represent whether it is A palindrome structure. Ensure that the length of the linked list is less than or equal to 900.
The main difficulty we encounter is that this is a one-way linked list. The node cannot be accessed forward. It needs to be able to "reverse order"
Idea 1:
- Find the intermediate node (for the speed pointer, see OJ (I))
- Linked list after intermediate node in reverse order
- Judge whether it is the same before and after
Illustration:
Code implementation:
//Returns the intermediate node of a linked list
//Fast and slow nodes
ListNode* middleNode(ListNode *head)
{
ListNode *slow,*fast;
fast=slow=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
//Reverse the linked list and return the new head node
// 1. Flip the linked list with three pointers
ListNode* reverseList1(ListNode* head)
{
ListNode *prev=NULL,*cur=head;
while(cur)
{
ListNode* next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}
//2. Flip the linked list with head insertion method
ListNode* reverseList2(ListNode* head)
{
ListNode* newHead=NULL;
ListNode* cur=head;
while(cur)
{
ListNode *next=cur->next;
cur->next=newHead;
newHead=cur;
cur=next;
}
return newHead;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
//Get intermediate node
ListNode* middle=middleNode(A);
//Reverse the linked list from the middle node
//ListNode* rHead=reverseList1(middle);
ListNode* rHead=reverseList2(middle);
while(A&&rHead)
{
if(A->val==rHead->val)
{
A=A->next;
rHead=rHead->next;
}
else
return false;
}
return true;
}
};
!!! This writing method is not recommended!!!
Because this writing method changes the structure of the incoming linked list, and our demand is to judge whether a linked list has a palindrome structure.
Idea 2 (realized by stack):
1. Find intermediate nodes
2. Stack the head to the intermediate node (not included)
3. Starting from the middle node, the stack top elements - > Val and cur - > Val are equal, and then they are out of the stack
4. Finally, judge whether the stack is empty
Code implementation:
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
ListNode *fast,*slow,*middle,*cur;
fast=slow=A;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
middle=slow;
stack<ListNode*> st;
for(cur=A;cur!=middle;cur=cur->next)
st.push(cur);
for(cur=middle;cur;cur=cur->next)
{
if(st.top()->val==cur->val)
st.pop();
}
if(st.empty())
return true;
return false;
}
};
3. Cross linked list
Title Link: 160. Intersecting linked list
Title Description:
Here are the head nodes headA and headB of the two single linked lists. Please find and return the starting node where the two single linked lists intersect. If there is no intersecting node between the two linked lists, null is returned.
As shown in the figure, two linked lists intersect at node c1:
Source: LeetCode
Idea:
It is easy to judge whether the linked lists intersect. Both linked lists go to the end and see whether the last node is the same (because the linked list intersection must be an inverted Y-type, not an X-type)
We also need to return the first intersection node. If the two linked lists have the same length, we can traverse together. If the nodes are the same, we can return directly.
In the case of different lengths, the long ones can take the gap step first, and then go together
Code implementation:
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pa=headA,*pb=headB;
int lenA=1,lenB=1;
while(pa->next)
{
lenA++;
pa=pa->next;
}
while(pb->next)
{
lenB++;
pb=pb->next;
}
if(pa!=pb)
return NULL;
ListNode *shortList=headA,*longList=headB;
if(lenA>lenB)
{
shortList=headB;
longList=headA;
}
int gap=abs(lenA-lenB);
while(gap--)
longList=longList->next;
while(shortList&&longList)
{
if(shortList==longList)
return longList;
longList=longList->next;
shortList=shortList->next;
}
return NULL;
}
};
4. copy the linked list with random pointer
Title Link: 138. Copy linked list with random pointer
Title Description:
You can add an extra pointer to any node in the list or random dom.
Construct a deep copy of this linked list. The deep copy should consist of exactly n new nodes, in which 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 replication linked list, and these pointers in the original linked list and replication linked list can represent the same linked list state. The pointer in the copy linked list should not point to the node 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 copy linked list also have x.random -- > y.
Returns the header node of the copy linked list.
Source: LeetCode
Schematic diagram (from buckle):
This question is the most difficult one in this blog. It is challenging both in thinking and code control
First, we need to understand deep copy
This is a concept opposite to shallow copy in C + +. We don't have much in-depth discussion here (I'll discuss it in-depth in the C + + topic later)
It can be understood here that we can apply for nodes in memory, and then connect these nodes according to the linked list connection
"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 copied linked list also have x.random -- > y"
It is a process of * * imitating the cat and drawing the tiger * *.
analysis:
Without the random pointer, this process is very simple. Traverse the original linked list, copy a current node, and create a new list in order.
But with the random pointer, the problem becomes complicated.
The main reason is that in the original table, we can know which node the random pointer of a node points to through the random pointer, but in the process of creating a new table, we can't find which node in the new table the random pointer of the new table should point to (that is, there is no connection between the new table and the original table node)
To solve this problem at this time, we must establish a connection between the original table and the new table
We take this approach:
Connect the copy node you applied for to the back of the original node.
In this way, the latter of the original node found through the random pointer is the copy node pointed to by the random pointer of the corresponding copy node in the new table.
Image analysis:
Solution:
1. Connect the copy node to the back of the original node
2. Handle the random pointer of the copy node
3. Cut the copy node from the original linked list and connect it to form a new list
Code implementation:
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head)
{
//1. Connect the copy node to the back of the original node
Node* cur=head;
while(cur)
{
Node* next=cur->next;
Node* copy=(Node*)malloc(sizeof(Node));
copy->val=cur->val;
copy->next=next;
cur->next=copy;
cur=next;
}
//2. Handle the random pointer of the copy node
cur=head;
while(cur)
{
Node* copy=cur->next;
if(!(cur->random))
copy->random=NULL;
else
copy->random=cur->random->next;
cur=copy->next;
}
//3. Cut off the copy node and connect it
cur=head;
Node *copyhead,*copytail;
copyhead=copytail=NULL;
while(cur)
{
Node* copy=cur->next;
if(copyhead==NULL)
copyhead=copy;
else
copytail->next=copy;
copytail=copy;
cur=cur->next=copy->next;
}
return copyhead;
}
🤗 Now our blog is coming to an end.
😊 I hope you can gain something after reading!!! This will be my greatest inspiration!
It's not easy to type codes, code words and draw pictures. I'm looking forward to a little praise ❤❤
If you have any doubts about the content of the blog or about the thinking problem, you are welcome to communicate and discuss with me ✔
All the codes in this issue will be transferred to my gitee warehouse and can be downloaded if necessary
Warehouse portal: data structure
See you next blog! 😘