preface
🍃 hello everyone!!! I'm a Java ape~
🍄 Because of the epidemic situation, the dormitory is closed. It's good not to run around and add chaos to the society.
🌸 Because there is nothing to do in the dormitory, but you can't fall behind to learn, so brush a few OJ questions in the linked list to consolidate what you have learned before. Here are some problem-solving methods to share. I hope you can learn from each other. Welcome to visit again!!!
🌿 In the new year, I wish you a happy year of the tiger!!! 🐅🦁🐅
💪 Finally, I hope the epidemic will end soon. Come on, Shaanxi! Come on, Chang'an!!!
catalogue
LeetCode 203 removing linked list elements
LeetCode 876 intermediate node of linked list
The penultimate node in the Offer 22 lin k ed list
LeetCode 21 merges two ordered linked lists
Leetcode interview question 02.04 Split linked list
LeetCode 234 palindrome linked list
LeetCode 160 cross linked list
LeetCode 203 removing linked list elements
Title Link: Remove linked list elements
Title: give a linked list and an integer, delete all nodes in the linked list whose value is the integer, and return the deleted linked list.
Example:
Title Analysis: delete all nodes in the linked list, and return the head node of the deleted linked list if the element is equal to an integer.
🤔 Idea: traverse the linked list and compare with the given value. If the value of the node is equal to the given value, delete the node. The deletion of the linked list node needs to mark the previous node of the deleted node. The specific steps are as follows:
1. First, empty the linked list. If the linked list is empty, return the empty linked list to the row
2. Give two marks, cur marks the nodes traversed in turn, and pre marks the previous node of cur
3. Judge whether the node to be deleted is the head node. If it is the head node, update the head node, because the title requires to return the head node of the deleted linked list. The method to judge the head node is pre null
4. If it is not a header node, it can be deleted normally
👁🗨 Reference code:
class Solution {
public ListNode removeElements(ListNode head, int val) {
//Air judgment
if(head == null){
return head;
}
ListNode cur = head;
ListNode pre = null;
while(cur != null){
if(cur.val == val){
if(pre == null){ //Delete node as head node
head = cur.next; //Update header node
cur = head;
}else{
pre.next = cur.next;
cur = pre.next;
}
}else{ //If the current node is not the node to be deleted, traverse in turn
pre = cur;
cur = cur.next;
}
}
return head;
}
}LeetCode 876 intermediate node of linked list
Title Link: Intermediate node of linked list
Title: for a non empty single linked list with head node, return the intermediate node of the linked list. If there are two intermediate nodes, return the second intermediate node.
Title Analysis: if the linked list has an odd number of nodes, the middle node will be returned. If the linked list has an even number of nodes, the middle two later nodes will be returned. Drawing Description:
🤔 Idea: fast and slow pointer method: a fast pointer fast and a slow pointer slow. The two pointers traverse the linked list at the same time. When the fast pointer reaches the end, the slow pointer just goes to the middle position. Drawing Description:
Specific steps:
1. fast pointer and slow pointer traverse successively
2. Traversal condition: fast= null && fast. next != null
3. Finally, when the traversal conditions are not satisfied, slow is returned
👁🗨 Reference code:
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}The penultimate node in the Offer 22 lin k ed list
Title Link: The penultimate node in the lin k ed list
Title: enter a linked list and output the penultimate node in the linked list. In order to conform to the habit of most people, this question starts from 1, that is, the tail node of the linked list is the penultimate node.
Example:
🤔 Idea: This provides a clever method: give the two pointers fast, slow, fast go first and slow go later. Both pointers traverse from the chain header. When fast goes through k nodes, slow starts to go from the head, while fast continues to go back from the current node. When fast goes to null, the node corresponding to slow is the node to return. The specific steps are as follows:
1. fast starts to complete k nodes
2. slow and fast start at the same time and take one step at a time
3. When fast reaches the end of the linked list, slow is the node to be returned
👁🗨 Reference code:
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while(k > 0){
fast = fast.next;
k--;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}LeetCode 21 merges two ordered linked lists
Title Link: Merge two ordered linked lists
Title: merge two ascending linked lists into a new ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists. Example:
Title Analysis: give two ascending linked lists and combine the two ascending linked lists into one ascending linked list
🤔 Idea: for this problem, we can create a new linked list and compare the elements of the two linked lists in turn. Which element is small will be linked in the new linked list and cycle in turn. When the nodes of a linked list have been linked in the new linked list, the remaining nodes of another linked list will be directly linked in the new linked list. The specific steps are as follows:
1. Create a new linked list first
2. Traverse and compare the elements of the two linked lists in turn
3. Insert the node with small element into the new linked list and continue the comparison
4. When all the elements of a linked list are inserted into the new linked list, the rest of the other linked list is linked to the end of the new linked list
👁🗨 Reference code:
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode list3 = new ListNode(0);
ListNode cur = list3;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
cur.next = list1;
cur = cur.next;
list1 = list1.next;
}else{
cur.next = list2;
cur = cur.next;
list2 = list2.next;
}
}
if(list1 != null){
cur.next = list1;
}
if(list2 != null){
cur.next = list2;
}
return list3.next;
}
}Leetcode interview question 02.04 Split linked list
Title Link: Split linked list
Title: give you a head node of the linked list and a specific value X. please separate the linked list so that all nodes less than x ， appear before nodes greater than or equal to X ，. Example:
Topic analysis: give a linked list and a specific value, compare the value in the linked list with the given value, and arrange the nodes less than the given value in the front of the linked list, and the rest in the back according to the starting order.
🤔 Idea: we can create two linked lists, insert the nodes less than the given value into the first linked list, insert the remaining nodes into the second linked list, and finally link the two linked lists. The specific steps are as follows:
1. Empty the linked list. If the linked list is empty, return the empty linked list
2. new two new linked lists
3. Traverse the linked list, insert the nodes less than the given value into the first linked list, and insert the remaining nodes into the second linked list
4. Link two linked lists. The tail of the first linked list links the head of the second linked list
5. The tail of the second linked list can point to empty
👁🗨 Reference code:
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null){
return head;
}
ListNode headL = new ListNode(0);
ListNode curL = headL;
ListNode headR = new ListNode(0);
ListNode curR = headR;
ListNode cur = head;
while(cur != null){
if(cur.val < x){
curL.next = cur;
curL = cur;
cur = cur.next;
}else{
curR.next = cur;
curR = cur;
cur = cur.next;
}
}
curL.next = headR.next;
curR.next = null;
return headL.next;
}
}LeetCode 234 palindrome linked list
Title Link: Palindrome linked list
If the structure of the linked list is true, a reply will be returned if the structure of the linked list is false
Title Analysis: the so-called palindrome structure is that the positive and negative are the same, such as 12321123321. This structure is the palindrome structure.
🤔 Idea 1: we can save the node elements of the linked list in the array, and then judge whether the array is palindrome. The specific steps are as follows:
1. new an ArrayList, which is used to save the node elements of the linked list
2. Traverse the linked List and save the node elements of the linked List in the List
3. Take an element from the head of the List and an element from the tail for comparison. If it is the same, carry out the next round of comparison. If it is different, return false
4. When the linked list is traversed and all are the same, return true
👁🗨 Reference code:
class Solution {
public boolean isPalindrome(ListNode head) {
//Copy the value into the array to determine whether the array is palindrome
List<Integer> list = new ArrayList<>();
ListNode cur = head;
while(cur != null){
list.add(cur.val);
cur = cur.next;
}
int left = 0;
int right = list.size()-1;
while(left < right){
if(list.get(left) == list.get(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}🤔 Idea 2: we can split the linked list, then reverse the latter half of the linked list, and then compare the reverse part with the first half in turn. If the values of the nodes are the same, it is a palindrome, otherwise it is not a palindrome structure. The specific steps are as follows:
1. Split linked list, as mentioned in the previous question, you can refer to the previous question
2. Reverse linked list, which was also mentioned earlier, is attached with a link. If you can't, you can click the link to learn, LeetCode206 - reverse linked list (Java implementation, illustrated)_ CSDN blog
3. Compare
Note: this idea involves the segmentation and inversion of the linked list, so it should be studied as a key problem
👁🗨 Reference code:
class Solution {
public ListNode getMid(ListNode head){
ListNode fast = head;
ListNode slow = head;
ListNode pre = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
pre = slow;
slow = slow.next;
}
if(fast != null){
return slow;
}else{
return pre;
}
}
public ListNode reverse(ListNode head){
ListNode cur = head;
ListNode next = null;
ListNode pre = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
public boolean isPalindrome(ListNode head) {
ListNode mid = getMid(head);
ListNode B = mid.next;
B = reverse(B);
ListNode curB = B;
ListNode curA = head;
while(curB != null){
if(curA.val != curB.val){
return false;
}
curA = curA.next;
curB = curB.next;
}
return true;
}
}LeetCode 160 cross linked list
Title Link: Intersecting linked list
Title: for the head node of the two linked lists, return the starting node of the two linked lists. If they do not intersect, return null
Topic analysis: there are two linked lists. The linked list may intersect. If it intersects, the starting node of the intersection will be returned. If it does not intersect, null will be returned
🤔 Idea: first, judge whether the linked list intersects. Judgment basis: if the two linked lists intersect, the tail nodes of the two linked lists must be the same. Before intersection, the two linked lists may be the same or different in length, corresponding to the following situations:
For the case of traversal, the first node can be found directly on the left
For the case on the right, you can count the length of the two linked lists first. Whichever is longer, you can go through the excess length first. After walking, the two linked lists traverse at the same time, which forms the case on the left, that is, you can find the intersection node soon
Specific steps:
1. Empty judgment. If a linked list is empty, it must not intersect and return null directly
2. Count the number of nodes in the two linked lists and make a difference between the number of nodes corresponding to the two linked lists
3. After counting the number, both linked lists reach the end. Judge whether the end nodes are the same. If they are different, it indicates that there is no intersection, and return null
4. If the difference is greater than 0, it indicates that the first linked list is long, and the difference is one length first
5. If the difference is less than 0, it indicates that the second linked list is long, and the difference is one length first
6. Traverse the two linked lists in turn, find the same node, and then return
👁🗨 Reference code:
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode curA = headA;
int sizeA = 1;
while(curA != null){
sizeA++;
curA = curA.next;
}
ListNode curB = headB;
int sizeB = 1;
while(curB != null){
sizeB++;
curB = curB.next;
}
if(curA != curB){
return null;
}
curA = headA;
curB = headB;
int alm = sizeA - sizeB;
if(alm >= 0){
while(alm > 0){
curA = curA.next;
alm--;
}
}else{
while(alm < 0){
curB = curB.next;
alm++;
}
}
while(curA != curB){
curA = curA.next;
curB = curB.next;
}
return curA;
}
}