This column will start from the basics and progress step by step, brushing an algorithm question every day, and please support me a lot. Although the data structure is difficult, as long as you stick to it, you will be able to learn it well, and I hope everyone can benefit from it.
Column address: An algorithm question column every day Data Structure Column
Online brushing website: Niuke.com
are you ready
Let's go!
foreword
- I recommend to everyone an artifact for writing questions and interviews. I also use this artifact to study! ~ The link is as follows: Brush question artifact jump link
- The artifact not only has a very beautiful web interface, but it is also very easy to operate and get started! It is very suitable for beginners to study systematically!
- Novices can use this artifact to do daily quizzes, read the facebooks of big factories, learn basic computer knowledge, and communicate face-to-face with Daniels~ The pictures of the quizzes have been placed below~
Q1: Reverse linked list
👀 Problem description
Topic source: Niuke.com
✏️ Thought analysis and problem solving
Solution 1, create a new linked list and a sentinel node (because there is no return, the sentinel node is required to record the position of the head node), traverse the two ordered linked lists list1 and list2, because the ascending order is required, then whoever takes the smaller will make the new linked list The next node, whichever node is taken, will be shifted backward until the trailing null.
public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null){ return list2; } if(list2==null){ return list1; } ListNode result = new ListNode(-1); ListNode guard = result;//Sentinel node, very important while(true){ if(list1 == null && list2 == null){//It's all over, it's over. break; } if(list1==null){//After list1 is taken, all the following ones are taken from list2. result.next = list2; list2 = list2.next; result = result.next; }else if(list2 == null){//After list2 is taken, all the following ones are taken from list1. result.next = list1; list1 = list1.next; result = result.next; }else if(list1.val<=list2.val){//Like arrays, whoever takes the smaller result.next = list1; list1 = list1.next; result = result.next; }else if(list1.val>list2.val){//Like arrays, whoever takes the smaller result.next = list2; list2 = list2.next; result = result.next; } } return guard.next; }
Solution 2: Optimize solution 1. It is observed that if you want to use up a linked list, you can directly point to its head node, omitting the step of taking the remaining nodes in solution 1.
public ListNode Merge(ListNode list1,ListNode list2) { if(list1==null){ return list2; } if(list2==null){ return list1; } ListNode result = new ListNode(-1); ListNode guard = result; while(list1!=null && list2!=null){ if(list1.val<=list2.val){//Same solution one result.next = list1; list1 = list1.next; result = result.next; }else if(list1.val>list2.val){//Same solution one result.next = list2; list2 = list2.next; result = result.next; } } if(list1==null){//Optimization point, all remaining nodes take list2 result.next = list2; } if(list2==null){//Optimization point, all remaining nodes take list1 result.next = list1; } return guard.next; } }
The third solution is to use recursion. The idea is to compare the head nodes of list1 and list2 each time. Whoever is smaller is the head node, and then continues to compare. This step is the same for every step.
public ListNode Merge(ListNode list1,ListNode list2) { //Exit conditions if(list1==null){ return list2; } //Exit conditions if(list2==null){ return list1; } ListNode guard = null; //Whoever is younger is the head node, and then continue to repeat this step if(list1.val>=list2.val){ guard = list2; guard.next = Merge(list1,list2.next); }else{ guard = list1; guard.next = Merge(list1.next,list2); } return guard; }
After the article: The artifact of brushing questions
Click on the link to jump to register and start your nanny-level problem-solving journey! The road of brushing questions and fighting monsters
In addition, there are not only questions here, but also everything you want, which is very suitable for beginners and beginners to learn~
1. Algorithms (398 questions): 100 questions for interviews, introduction to algorithms, and high-frequency list of interviews
2. Data Structures (300 questions): All are very classic linked lists, trees, heaps, stacks, queues, dynamic programming, etc.
3. Language (500 questions): C/C++, java, python introductory algorithm exercises
4. SQL (82 questions): Quick Start, SQL Must Know, SQL Advanced Challenge, Interview Questions
5. The real questions of the written test of Dachang: ByteDance, Meituan, Baidu, Tencent... Mastering experience is not afraid of interviews!