Article directory
- Exchange the nodes in the linked list two by two
-
- Problem Description
- Enter description
- output description
- input example
- output example
- answer
-
- full code
- Discussion on invalidity of swap(p,q)
- to feel
- Talking about IT class
-
- What are the pros and cons
- other ways
Pairwise exchange of nodes in the linked list
Description of the problem
Given a linked list, exchange the adjacent nodes in it two by two, and return the exchanged linked list.
You can’t just change the value inside the node, but you need to actually swap the node.
Enter a description
First enter the length of the linked list len, and then enter len integers separated by spaces.
Output description
See output format example
Input example
4
1 2 3 4
Example output
head–>2–>1–>4–>3–>tail
Problem solution
Complete code
The problem is not difficult, the complete code and comments are as follows:
#include<iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct ListNode
{<!-- -->
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {<!-- -->}
ListNode(int x) : val(x), next(NULL) {<!-- -->}
ListNode(int x, ListNode *next) : val(x), next(next) {<!-- -->}
};
class solution
{<!-- -->
public:
ListNode* swapPairs(ListNode* head)
{<!-- -->
//Fill this function to complete the function
ListNode* p=head,*q,*fade_head;
fade_head = new ListNode;
fade_head->next =head;
ListNode *mark = fade_head;//direct to the front node of swap(p,q)
//len
int len = 0;
while(p)
{<!-- -->
len + + ;
p=p->next;
}
if(len >1)
{<!-- -->
//deal
p=head;
int tot=0;
while(p)
{<!-- -->
tot + + ;
if(tot == 2)//swap(p,q), guarantees the existence of q
{<!-- -->
//swap(p,q)
mark->next =p;
q->next = p->next;
p->next = q;
//init
mark = q;
tot=0;
q=p;//The previous p and q nodes have changed positions
p=q->next;
}
//
q=p;
p=p->next;
}
}
head = fade_head->next;
return head;
}
};
ListNode *createByTail()
{<!-- -->
ListNode *head;
ListNode *p1,*p2;
int n=0,num;
int len;
cin>>len;
head=NULL;
while(n<len & & cin>>num)
{<!-- -->
p1=new ListNode(num);
n=n + 1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
void displayLink(ListNode *head)
{<!-- -->
ListNode *p;
p=head;
cout<<"head-->";
while(p!= NULL)
{<!-- -->
cout<<p->val<<"-->";
p=p->next;
}
cout<<"tail\\
";
}
int main()
{<!-- -->
ListNode* head = createByTail();
head=Solution().swapPairs(head);
displayLink(head);
return 0;
}
Discussion on the invalidity of swap(p,q)
p and q are adjacent nodes
The idea of swap() appears in the following function,
class Solution
{<!-- -->
public:
ListNode* swapPairs(ListNode* head)
{<!-- -->
//Fill this function to complete the function
ListNode* p=head,*q,*fade_head;
fade_head = new ListNode;
fade_head->next =head;
ListNode *mark = fade_head;//direct to the front node of swap(p,q)
//len
int len = 0;
while(p)
{<!-- -->
len + + ;
p=p->next;
}
if(len >1)
{<!-- -->
//deal
p=head;
int tot=0;
while(p)
{<!-- -->
tot + + ;
if(tot == 2)//swap(p,q), guarantees the existence of q
{<!-- -->
//swap(p,q)
mark->next =p;
q->next = p->next;
p->next = q;
//init
mark = q;
tot=0;
q=p;//The previous p and q nodes have changed positions
p=q->next;
}
//
q=p;
p=p->next;
}
}
head = fade_head->next;
return head;
}
};
one of them
q->next = p->next;
p->next = q;
I was thinking of using swap(p,q) to be lazy, and finally updated the pointing relationship of the previous node of p and q, and it was ok. The output was the same as the input, and I was still struggling. Is the content of the p and q nodes changed, but the position remains the same [p, q pointing has changed], or the content remains the same, the position of p, q has changed [the position of the p, q node has changed], Laugh at yourself, exchange pointers, I should hand-write the exchange node position, after the exchange, the pointers of p and q can be changed again, this idea is still familiar.
Feel
Special operations on linked list topics, special cases considered Empty list, 1, 2, why should we consider 2 nodes?
For example, if the node is inserted backwards, the current operation node may overlap with the last node, resulting in a bug.
Talking about IT classes
What are the pros and cons
1) Benefit
- Learn professional knowledge
IT training courses provide systematic professional knowledge and skills training to help trainees fully master the knowledge in the IT field and improve their skills - Gain hands-on experience
Training courses usually provide practical projects and experiments, allowing students to learn and apply what they have learned in practical operations, and gain real practical experience - develop problem-solving skills
The training class focuses on cultivating students’ ability to solve problems. By solving practical problems, train students’ logical thinking and problem-solving ability - Learn about teamwork
The training class arranges trainees to carry out team projects, so that trainees can learn to cooperate effectively with others and enhance teamwork ability - Get in touch with the latest technology
The IT industry is developing rapidly, training courses can allow students to get in touch with the latest technology and development trends, and maintain industry sensitivity - Career Development Opportunities
Obtain a certificate after completing the training course, adding advantages to job hunting, many companies prefer to hire candidates with relevant training experience - Expand your network
Meet like-minded classmates and professional mentors in the industry in the training class, build a network of people, and help personal career development
2) Disadvantages
- Fees
Participation in training courses requires a certain fee, especially for some advanced and professional training courses, which are relatively expensive, which may put a certain pressure on the students’ finances - Time commitment
Training courses usually require students to devote a lot of time to study and participate in practical projects, which may be busy for students who have work or other learning tasks - Variation in quality
The competition in the training course market is fierce, and the quality varies from good to bad. Choosing an inappropriate training class may result in acquired knowledge and skills that do not meet actual needs, wasting time and money - Self-study costs
Some people may have a certain self-study ability, and they can also acquire certain IT knowledge through self-study on the Internet and books, avoiding the cost and time investment of training courses - Study load
For students who already have a certain IT foundation, the training course may appear too simple, resulting in uneven learning load
Therefore, participating in IT training courses has many advantages, which can improve learning effects and professional competitiveness, and help students master professional knowledge and skills. However, it is important to choose the right training course, considering the cost, time investment and quality of the training course. Self-study is also a good choice for students with self-study ability. The final decision will be weighed against individual circumstances and learning goals.
Other ways
-
Self-study
Take advantage of the rich resources on the Internet, such as online tutorials, documents, teaching videos, etc., to learn IT knowledge by yourself. Self-study requires good self-discipline and study planning, but it can also achieve good learning results. -
OpenCourseWare
Some universities, educational institutions, or online education platforms offer open courses that can be studied for free or at low cost. These courses can be in computer science, programming, network technology, etc. -
MOOC (Massive Open Online Course)
MOOC platforms such as Coursera, edX, Udemy, etc. provide a variety of computer science and IT-related courses, and students can freely choose the courses they are interested in. -
Book Reading
Reading IT-related professional books and reference materials can give you an in-depth understanding of knowledge and practical experience in specific fields. -
Participate in open source projects
– Actively participate in open source projects, contribute your own code and solve problems, you can learn a wealth of experience and skills in practice. -
Develop a study plan
Make a reasonable study plan, including learning objectives, content, time arrangement, etc., to help you learn IT knowledge in an orderly manner. -
Participate in technical communities
Join technical communities, technical forums, developer exchange groups, etc., to exchange experience and learning experience with other technical personnel. -
Practice project
Try to complete some practical projects, which help to apply theoretical knowledge to real situations and improve problem-solving skills.
Although taking IT training courses is a very effective way of learning, the methods mentioned above can also help individuals acquire knowledge. Ultimately, the choice of learning style should be a decision based on individual circumstances, learning goals and learning styles. Some may adapt to the instructor-led learning style of a workshop, while others may prefer self-directed learning and exploration. The important thing is to find the learning style that suits you, to continuously improve and improve your skills.