Understand the single – linked list often meet questions
Hello, following the understanding of basic sorting algorithm last time, this week, I summarized the basic knowledge of single linked list that I have learned and thought about and often meet the test questions, some of these questions are from “Sword Finger Offer”, some are from “Programmer code interview Guide”, some are from leetCode, not very comprehensive, but have some representative. I believe that after reading you must be like me, the algorithm of the interview and more confidence. However, the article is still smelly and long, I hope you can prepare coffee, ham sausage, instant noodles and so on, slowly read, if I have any wrong understanding, I also hope you can point out in the comment area for me, also be recognized for my code so many words.
What is a singly linked list
Linked list is a common basic data structure. It is a linear list, but it does not store data in a linear order. Instead, it stores Pointers to the next node in each node. They may not be contiguous because each node holds a reference (address) to the next node, so this is an advantage over arrays.
We often use the following code for a node in a singly linked list:
Public class Node{// Node value int value; // A pointer to the next Node (represented as a reference to the next Node in Java) Node next; public void Node(int value){ this.value = value; }}Copy the codeFeatures of single linked lists
- The time complexity of adding and deleting elements in the linked list is O(1), and the time complexity of searching an element is O(n).
- Single-linked lists do not preallocate storage space as arrays do, avoiding space waste
- A single linked list cannot be backtracked. For example, if you only know the first node of the list, you cannot quickly read the value of the last node of the fast list.
The basic operation of a single linked list
In the last video we talked about what a singly linked list is, so we all know that an array has basic operations to add, delete, change, or query. So singly linked lists, as a common type of data structure, also have these operations. So let’s look at the basic operations for singly linked lists:
Gets the length of a single linked list
Due to the memory address is not continuous singly linked list, the list does not have direct access to the function of the chain length of the table, for the length of a linked list, we can only to traverse the list of nodes at a time, until we find a node of the next node is empty when the total length of the chain table, the starting point of note that there is not an empty list then add node in turn, The first node of a linked list is given and the length of the list is obtained:
public int getLength(Node head){
if(head == null){
return 0;
}
int len = 0;
while(head ! = null){ len++; head = head.next; }return len;
}
Copy the codeQueries the node value of the specified index or the index of the specified deserving node value
Because a linked list is a discontinuous storage structure, the memory address of the node is not continuous, that is to say, the linked list cannot be indexed by the index value of the element like an array. So the time complexity of a linked list query is O(n), which is the same as the time complexity of an array query, because the memory location of what you’re looking for is not the same.
Public int getValueOfIndex(Node head, int index) throws Exception {getValueOfIndex(Node head, int index) throws Exception {if (index < 0 || index >= getLength(head)) {
throw new Exception("Out of bounds!");
}
if (head == null) {
throw new Exception("Current linked list is empty!");
}
Node dummyHead = head;
while(dummyHead.next ! = null && index > 0) { dummyHead = dummyHead.next; index--; }returndummyHead.value; } public int getNodeIndex(Node head, int value) {int index = -1; Node dummyHead = head;while(dummyHead ! = null) { index++;if (dummyHead.value == value) {
return index;
}
dummyHead = dummyHead.next;
}
return- 1; }Copy the codeAdd an element to the list
If you have learned data structure, you must know the operation of linked list insertion, including head insertion, tail insertion, and random node insertion. Of course, data structure is also used to insert an element in the case of an already constructed (save the list head node and tail node reference). It’s not so easy to insert an element when we only know the head of a list. For the head insert method, we just need to construct a new node and point the next pointer to the head of the list.
1. Insert a node in the head of an existing list
public Node addAtHead(Node head, int value){
Node newHead = new Node(value);
newHead.next = head;
return newHead;
}
Copy the codeInsert a node at the end of an existing list:
public void addAtTail(Node head, int value){ Node node = new Node(value); Node dummyHead = head; Note that this node is null when the next element of the element is emptywhile( dummyHead.next ! = null){ dummyHead = dummyHead.next; } dummyHead.next = node; }Copy the code3. Add a node at the specified location
Public Node insertElement(Node head, int value, Throws Exception {// For convenience here we assume we know the length of the list int length = getLength(head);if (index < 0 || index >= length) {
throw new Exception("Out of bounds!");
}
if (index == 0) {
return addAtHead(head, value);
} else if (index == length - 1) {
addAtTail(head, value);
} else {
Node pre = head;
Node cur = head.next;
//
while(pre ! = null && index > 1) { pre = pre.next; cur = cur.next; index--; } // after the loop ends, pre stores the previous Node of the index and cur stores the current Node of the index Node = new Node(value); pre.next = node; node.next = cur; }return head;
}
Copy the codeTo add a node at the specified location, we should first find the previous node of the index and the node, record the two nodes respectively, and then set the next pointer of the previous node of the index to the new node, and then set the next pointer of the new node to the insert node. If you insert an element into an array at the specified index position, then the index position (memory address) of the element after that index position will change. So the insertion time of an array is O(n); So linked lists are more efficient to insert than arrays, and delete as well.
The linked list deletes an element
Because the above introduced the method of adding elements to the list, here is not a detailed introduction to the method of deleting nodes from the list directly given the code:
1, delete the head node, i.e. delete the node whose index is 0:
public Node deleteHead(Node head) throws Exception {
if (head == null) {
throw new Exception("Current linked list is empty!");
}
return head.next;
}
Copy the code2. Delete the tail node
public void deleteTail(Node head) throws Exception {
if (head == null) {
throw new Exception("Current linked list is empty!");
}
Node dummyHead = head;
while(dummyHead.next ! = null && dummyHead.next.next ! = null) { dummyHead = dummyHead.next; } dummyHead.next = null; }Copy the codeAlter table alter table alter table alter table alter table
public Node deleteElement(Node head, int index) throws Exception {
int size = getLength(head);
if (index < 0 || index >= size) {
throw new Exception("Out of bounds!");
}
if (index == 0) {
return deleteHead(head);
} else if (index == size - 1) {
deleteTail(head);
} else {
Node pre = head;
while(pre.next ! = null && index > 1) { pre = pre.next; index--; } // At the end of the loop, pre saves the last node of the index and points it to the next element of the indexif (pre.next != null) {
pre.next = pre.next.next;
}
}
return head;
}
Copy the codeAs can be seen from the addition and deletion of a single linked list, when a linked list wants to operate on a specified index (add, delete), it must obtain the previous element of the index. Remember this sentence is very useful for linked list problems.
Single – linked lists often meet questions
After introducing the common operations of linked lists, our goal is to learn the common interview questions of linked lists. Otherwise why would we learn them? Ha ha ~ just kidding, so we’ll start with simple interview questions:
Find the middle element of a single linked list
If you’re laughing at this interview question, why is it so easy? Just pick up the pen, go through the list, get len, go through the list again and the element at len over 2 is the middle element.
We can not say that this method is wrong, think about a Tencent interviewer sitting opposite to ask this question, this answer is obviously even their own this pass is difficult to pass. So what’s a more gradual way to do it? Or a less time intensive way to do this lookup? One of the key concepts that comes out of this is the fast and slow pointer, which is what the interviewer is looking for.
Suppose we set two Pointers slow and fast to start at the head of a single list. Fast is twice as fast as slow. When fast points to the end node, slow is right in the middle. If you think about it for a moment, if we have a list of 6, slow moves one node at a time, and fast moves two at a time, then slow = 2 moves exactly to the node at 2 when fast = 5.
So the solution idea of solving the middle element of the linked list is as follows:
public Node getMid(Node head){
if(head == null){
returnnull; } Node slow = head; Node fast = head; // fast.next = null indicates that FAST is the last node of the listwhile(fast ! = null && fast.next ! = null){ fast = fast.next.next; slow = slow.next; }return slow;
}
Copy the codeCheck if a linked list is a circular list
First of all, this problem is also a study of the fast and slow pointer, is the second application of the fast and slow pointer. Let’s talk a little bit about what a circular list is. A circular list is actually a single list whose tail pointer points to the head pointer. It’s called a circular list. For example 1 -> 2 -> 3 -> 1 -> 2….. . Why do fast and slow Pointers always meet in a recirculating list? You can imagine two people in A race, A is fast, B is slow, after A certain amount of time, A will always meet B, and the total distance A has run when they meet minus the total distance B has run must be n times the lap length. This is also known as Floyd’s ring detection algorithm.
How to use the fast or slow pointer to determine whether a linked list is a circular list?
private static boolean isLoopList(Node head){
if (head == null){
return false; } Node slow = head; Node fast = head.next; // If it is not a circular list then there must be a tail nodewhile(slow ! = null && fast ! = null && fast.next ! = null){if (fast == slow || fast.next == slow){
return true; } // Slow one step at a time fast = fast.next-next; slow = slow.next; } // return if it is not a circular listfalse
return false;
}
Copy the codeWe have a single linked list and we find the NTH node
If we let the fast pointer take n-1 steps first, and then let the slow pointer start. The fast and slow Pointers only move one position at a time. When the fast pointer moves to the end of the list, is the slow pointer in the position of the NTH node from the bottom?
It is not correct to call these two hands fast or slow, because fast or slow means that one is moving faster and the other is moving slower. In this case, the fast hand only moves n-1 positions before the slow hand, and moves at the same speed.
If the above explanation is not easy to understand, here is another idea, which is to imagine that the above moving process of fast and slow Pointers is equivalent to a sliding window with a fixed window size of N:
- When n = 1 fast does not move and fast reaches the last node, i.e., fast. Next, slow also reaches the tail node full condition
- N = len The fast pointer moves n-1 (len-1) times to reach the last node, and slow is at the head node. Both critical values satisfy our assumption.
- If 1< n < len, we assume n = 2, then fast moves one step earlier than slow, i.e., the window size is 2. If fast. Slow is the next-to-last node.
Let’s look at the function implementation:
Private Node getLastIndexNode(Node head, int n) {// The input list cannot be empty and n is greater than 0if (n < 1 || head == null) {
returnnull; } n = 10; // Node fast = head; // The penultimate KTH node and the penultimate node are separated by n-1 positions // the fast takes n-1 positions firstfor(int i = 1; i < n; I++) {// indicates that there are nodesif(fast.next ! = null) { fast = fast.next; }else{// There are no nodes, but I has not reached k-1, indicating that k is too large and there are not many elements in the listreturnnull; } } Node slow = head; // Fast has not reached the end of the list yet, so fast and slow go together. // When fast reaches the last node, i.e., fast. Next =null, slow is the NTH node from the bottomwhile(fast.next ! = null) { slow = slow.next; fast = fast.next; } // return the resultreturn slow;
}
Copy the codeDelete the penultimate node of a singly linked list
See this problem when happy, this knowledge point is not an evolutionary version of the solution to the NTH node. But we also said that if you want to operate on a node in a linked list (add, remove) you also need to know the previous node of that node. So if we delete the NTH element we have to find the NTH + 1 element. The next pointer p.ext to the penultimate n + 1 element p points to p.ext.next.
When we find the penultimate NTH node, we let FAST take n-1 steps first, so when we delete the penultimate NTH node, we need to let FAST take n steps first, build a window of n+1 size, and then move fast and slow to the end of the linked list as a whole. The node that slow points to is the NTH +1 node from the bottom.
Here we can also use the sliding window idea to consider thresholds:
-
When n = 1, the window we need to build is 2, that is, when fast. Next = null, slow is on the penultimate node of, so it can be imagined that our conditions are met.
-
When 1 < n < len, we can always build a window with the size of Len + 1. When n is at most len-1, slow is in the head node, fast is in the non-node, and the penultimate element is deleted, that is, the second node with the positive number is deleted. Slow. Next = slow. Next.
-
When n > len, you can imagine that the NTH element that we’re looking for doesn’t exist, so we just return the head node
-
If n = len, the loop does not terminate because len does not exist, and fast = fast.next; At the end of the loop, fast points to null, and slow is at the head node, so the node we want to delete is the head node. We just need to determine at the end of the loop if fast == null return head.next
Let’s look at the solution:
/**
* 删除倒是第 n 个节点 我们就要找到倒数第 n + 1 个节点， 如果 n > len 则返回原列表
*/
private Node deleteLastNNode(Node head, int n) {
if (head == null || n < 1) {
returnhead; } Node fast = head; // Note that we are building a window of length n + 1 so I starts at 0for(int i = 0; i < n; I++) {// when the fast pointer points to the penultimate node, it removes the head nodeif (fast == null) {
return head;
} else{ fast = fast.next; }} // The loop is complete when n = len or fast = nullif (fast == null){
returnhead.next; } // N must be less than len and the fast has taken n steps first.while(fast.next ! = null) { fast = fast.next; pre = pre.next; } pre.next = pre.next.next;return head;
}
Copy the codeRotate a single linked list
Given a linked list, rotate the list so that each node moves k positions to the right, where k is a non-negative number. Given list for 1 – > 2 – > 3 – > 4 – > 5 – > NULL and k = 2, 4 – > return 5 – > 1 – > 2 – > 3 – > NULL.
And then we’re done, we’re going to delete the NTH node from the bottom, and we’re looking at whether this is going to be easy, but the essence of this problem is to find the k node and turn it into the tail node, and then the last node of the original list points to the original head node
private Node rotateList(Node head, int n) { int start = 1; Node fast = head; // Let the fast pointer move n to give a positionwhile(start < n && fast.next ! = null) { fast = fast.next; start++; } // If fast. Next = null means that n is exactly the length of the original list and no rotation is requiredif (fast.next == null || start < n) {
returnhead; } // if (0, 0, 0, 0, 0); Node newHead = fast. Next;while(fast.next ! = null) { fast = fast.next; } // The last node of the original list points to the original head node. // Change the last node of the rotated node to the last node.return newHead;
}
Copy the codeFlip single linked lists
Flipping a single linked list requires extra space complexity of O(1)
A node contains a reference to the next node. Flipping means that the original reference to the next node points to the previous node
- Find the next node of the current node to be flipped and save it in a variable because it will be flipped next
- Then make the next of the current node point to the previous node, which is initially null because the head node is flipped to become the tail node
- The current node to be reversed becomes the node before the next element to be compared, stored in a variable
- The current node to be compared is assigned to the next previously saved unflipped node
- When the current flipped node is null, the last saved node is the flipped list header
Ok, I don’t know if I can understand the flipping process of a linked list by following the steps I wrote above. If you don’t understand it, you can draw it yourself. Be careful to draw only one node at a time, and don’t consider the parts of the list that have been flipped.
Let’s look at the implementation process:
Public Node reverseList(Node head){// The last Node of the head Node is null Node pre = null; Node next = null;while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
}
Copy the codeFlip part of a singly linked list
0 < from < to < len
Flip the list from position to position. In fact, the flip process is similar, but we need to find the previous node in the from position, After flipping the from and to parts, the next pointer of the previous from node points to the flipped TO, and the flipped next pointer of the from node points to the next node of the flipped to node.
- The traversal process of the linked list requires counting the length of the linked list len, from the previous node of the node fPosPre, from the node at the beginning of the rollover from, to the node at the end of the rollover to, and tPosNext.
- After the loop, check whether the condition 0 < from < to < len is met. If not, return head
- The from to node is flipped
- After flipping, it is judged that if the flipped starting point is not head, head is returned. If the flipped linked list is the starting point, toPos is the head after flipping.
Now let’s look at the code (you may have a simpler solution that eliminates a few variables, but the following solution should be the best to understand);
private Node reversePartList(Node head, int from, int to) {
Node dummyHead = head;
int len = 0;
Node fPosPre = null;
Node tPosNext = null;
Node toPos = null;
Node fromPos = null;
while(dummyHead ! = null) {// Len is incremented by len++;if (len == from) {
fromPos = dummyHead;
} else if (len == from - 1) {
fPosPre = dummyHead;
} else if (len == to + 1) {
tPosNext = dummyHead;
} else if(len == to) { toPos = dummyHead; } dummyHead = dummyHead.next; } // Do not flip the linked list unless the condition is metif (from > to || from < 0 || to > len || from > len) {
return head;
}
Node cur = fromPos;
Node pre = tPosNext;
Node next = null;
while(cur ! = null && cur ! = tPosNext) { next = cur.next; cur.next = pre; pre = cur; cur = next; } // Return head if the start of the flip is not headif(fPosPre ! = null) { fPosPre.next = pre;returnhead; } // If the inverted list is the starting point, then the inverted toPos is the headreturn toPos;
}
Copy the codeSingly linked list sort
In my last article said to the array of basic sorting method Understand basic sorting method, for the list also has the above several kinds of sorting methods, if interested friends can also use the bubble sort, selection sort, quick sort to achieve singly linked lists of sorting, due to the linked list is back in the line, merge sort for a linked list is a good sort method. We know that merging can be done recursively, so it can also be done with a single linked list.
Merge sort of single linked lists
And the whole idea of merging is that if you have two lists, if you merge them in order. This is actually an interview question to merge two lists by the size of the elements so let’s first look at merging two lists we call this process merge.
Private Node merge(Node l, Node r) {// Create temporary space Node aux = new Node(); Node cur = aux; // Because the list can not easily get the length of the list, so generally usedwhileL == null indicates that the list traverses to the endwhile(l ! = null && r ! = null) {if (l.value < r.value) {
cur.next = l;
cur = cur.next;
l = l.next;
} else{ cur.next = r; cur = cur.next; r = r.next; }} // When half of the list is traversed, the other list must have only one element left.if(l ! = null) { cur.next = l; }else if(r ! = null) { cur.next = r; }return aux.next;
}
Copy the codeThe returned Node is the head of the list after merging. So the core process of merge sort is finished, think we want to merge an array will also need a mid divided operation center node is who, see whether this smiled, before we have talked about how to find a linked list in the middle of the element, so if everything is ok, ok, we to achieve the merge sort the list:
Private Node mergeSort(Node head) {// Head mergeSort(Node head) {// Head mergeSort(Node head)if (head == null || head.next == null) {
returnhead; } Node slow = head; Node fast = head; // Find the mid valuewhile(fast.next ! = null && fast.next.next ! = null) { slow = slow.next; fast = fast.next.next; } Node left = head; Node right = slow.next; If the last element of the list is set to null, then left is always equal to head and the list cannot be sorted. Left = mergeSort(left); right = mergeSort(right);return merge(left, right);
}
Copy the codeInsertion sort of single linked list
Recall the array of insertion sort, we started walking down from the second number group, if the current of the element value is bigger than the value of the next element, the next element should be before the current of the elements in an array, so we have sort of elements in the sequence from the forward scan, if the element (sorted) is greater than the new elements, Move the element to the next position (assign or swap). But because the list is not traceable, we can only start at the head of the list to find where this element should be.
Let’s look at the code implementation:
public Node insertionSortList(Node head) {
if (head == null || head.next == null) returnhead; Node dummyHead = new Node(0); Node p = head; dummyHead.next = head; // the value of p is not less than the next node elementwhile(p.next ! = null) {if (p.value <= p.next.value) {
p = p.next;
} else{//p points to 4 Node temp = p.ext; Node q = dummyHead; p.next = p.next.next; // Walk through the list to find the first element with a value smaller than the current temp value and insert the entire position after it between the head node and q nodewhile(q.next.value < temp.value && q.next ! = q) q = q.next; temp.next = q.next; // Rejoin the linked listelseQ.ext = temp; q.ext = temp; }}return dummyHead.next;
}
Copy the codeDivide the list
Title: Divide the linked list by a given value into new lists whose left value is less than this value and whose right value is greater than this value. For example, if a list is 1-> 4 -> 5 -> 2, given a number of 3, the divided list is 1-> 2 -> 4 -> 5
If the value of the node is smaller than the given value during the traversal, it will be divided into the left linked list, and vice versa. After traversal, it will be good to join the two linked lists. Look at the code without too much explanation.
private Node partition(Node head , int x){
if(head == null){
return = null;
}
Node left = new Node(0);
Node right = new Node(0);
Node dummyLeft = left;
Node dummyRight = right;
while(head ! = null){if(head.value < x){
dummyLeft.next = head;
dummyLeft = dummyLeft.next;
}else{
dummyRight.next = head;
dummyRight = dummyRight.next;
}
head = head.next;
}
dummyLeft.next = right.next;
right.next = null;
return left.next;
}
Copy the codeLists add and sum
Title: Given that each node in the list has a value between 0 and 9, the list as a whole can represent an integer. For example: 9->3->7 can represent 937 given two such lists, the head node is head1, head2 generates a new list of lists added together. The new linked list generated by 9->3->7 and 6 ->3 should be 1 -> 0 -> 0 -> 0
If you understand how to add two linked lists, you add each digit of the list in the order in which the last node is added, and if there is a carry, you add each digit of the list when the next node is added. This looks like math addition. So our solution is as follows:
- Flip the two lists you want to add so that you start adding from the last node of the original list.
- Synchronously traverses two reverse lists, adding the values of each node by using a variable to record whether or not to carry.
- So when the list is done and I’m looking for more carries and if I add another node,
- Flip the two lists again to restore them, and flip the new list to get the solution.
private Node addLists(Node head1, Node head2) { head1 = reverseList(head1); head2 = reverseList(head2); // carry identifier int ca = 0; int n1 = 0; int n2 = 0; int sum = 0; Node addHead = new Node(0); Node dummyHead = addHead; Node cur1 = head1; Node cur2 = head2;while(cur1 ! = null || cur2 ! = null) { n1 = cur1 == null ? 0 : cur1.value; n2 = cur2 == null ? 0 : cur2.value; sum = n1 + n2 + ca; Node node = new Node(sum % 10); System.out.println( sum % 10); ca = sum / 10; dummyHead.next = node; dummyHead = dummyHead.next; cur1 = cur1 == null ? null : cur1.next; cur2 = cur2 == null ? null : cur2.next; }if (ca > 0) {
dummyHead.next = new Node(ca);
}
head1 = reverseList(head1);
head2 = reverseList(head2);
addHead = addHead.next;
return reverseList(addHead);
}
private Node reverseList(Node head) {
Node cur = head;
Node pre = null;
Node next = null;
while(cur ! = null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } // Note that this returns an assignment to the current comparison elementreturn pre;
}
Copy the codeRemoves duplicate elements from ordered/unordered lists
Removes duplicate elements from an ordered list
It is relatively simple to delete duplicate elements in an ordered linked list. Because the linked list itself is ordered, if the element value is repeated, it must be adjacent. Therefore, the method of deleting duplicate elements is as follows:
For example, a linked list of 36 -> 37 -> 65 -> 76 -> 97 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 98 -> 37 -> 65 -> 76 -> 97 -> 98 -> 98
private void delSortSame(Node head) {
if (head == null || head.next == null) {
return;
}
Node dummy = head;
while(dummy.next ! = null) {if (dummy.value == dummy.next.value) {
dummy.next = dummy.next.next;
} else{ dummy = dummy.next; }}}Copy the codeRemoves duplicate elements from an unordered list
To delete duplicate elements in the unordered list, we must use a pointer to remember the previous element pre of cur and traverse all nodes after the cur element. If there are duplicates, the next pointer of the pre pointer points to when cur.next. Repeat through each node until the end of the list.
As a linked list prior to delete duplicate elements: 0 – > 0 – > 3 – > 5 – > 3 – > 0-1 – > > 4 – > 5 – > 7 after remove duplicate elements as: 0 – > 1 – > 3 – > 5 – > 4 – > 7
private void delSame(Node head) {
if (head == null || head.next == null) {
return;
}
Node pre = null;
Node next = null;
Node cur = head;
while(cur ! = null) {// The previous node of the element being examined pre = cur; // Next = cur.next; // Delete duplicate elements from the traversal remaining listwhile(next ! = null) {if(cur.value == next. Value) {// Delete the same element. }else{// move pointer pre = next; } // next = next. Next; } // look at the next element cur = cur.next; }}Copy the codeRearrange the list
In fact, this is also a series of problems, mainly to examine the operation of a linked list with O(1) extra space. Let’s start with the first question:
Rearrange and combine singly linked lists in terms of the left and right halves
Given a single linked list L: L0→L1→… → ln-1 →Ln, L0→Ln→L1→ ln-1 →L2→ ln-2 →… It is required that in-place operations must be performed without changing node values.
To rearrange the list, you must first find the middle node of the list, then separate the left and right lists, and then arrange the list in the order of the left and the right. If we assume that the list is radix, and the nodes at position N/2 count as the left half of the list, the right half of the list will have one more node than the left half of the list. When the left half of the list is the last node, we only need to set the remaining right half of the list as the next node. If N is even, N/2 + 1 is the start of the right list, and the last node of the left list is null, which happens to be null, so the last step of the rebeat is left. Next = right
Private void relocate1(Node head) {// If the list length is less than 2, no operation is requiredif (head == null || head.next == null) {
return; } // select * from the list where Node mid = head; Node right = head.next;while(right.next ! = null && right.next.next ! = null) { mid = mid.next; right = right.next.next; } // Right = mid.next; mid.next = null; // mergeLR(head, right) as required; } private void mergeLR(Node left, Node right) { Node temp = null;while(left.next ! = null) { temp = right.next; right.next = left.next; left.next = right; Next left = right. Next; right = temp; } left.next = right; }Copy the codeA rearranged list of headlines
Given a linked list 1 -> 92 -> 8 -> 86 -> 9 -> 43 -> 20 is characterized by odd bits ascending and even bits descending, it is required to rearrange the list and keep the whole list ascending
This problem is similar to the left and right half list. In fact, this can be interpreted as a list that has been rearranged, and now to perform the reverse process of the previous rearrangement. To satisfy this condition, we must assume that the node with the smallest even digits is greater than the element with the largest odd digits. I think that’s what they meant. Don’t bother if it’s not and we talked about merge sort, just merge once. Let’s look at the solution where the node satisfying the smallest digit is greater than the element with the largest odd digit:
How do you flip a linked list
Private Node relocate2(Node head) {// Create a new Node left = new Node(); Node right = new Node(); Node dummyLeft = left; Node dummyRight = right; int i = 0;while(head ! = null) {// Since I starts at 0, the head of the list is an odd number of bits, so I increment and then compare I ++;if (i % 2 == 0) {
dummyRight.next = head;
dummyRight = dummyRight.next;
} else{ dummyLeft.next = head; dummyLeft = dummyLeft.next; } // Set the next Node to null Node next = head.next; head.next = null; head = next; } right = reverseList(right.next); dummyLeft.next = right;return left.next;
}
Copy the codeDetermine that two singly linked lists (acyclic) intersect
Check whether two acyclic lists intersect. If they do, return the first node. If they do not, return null.
To analyze this problem, let’s assume that two single-linked lists intersect, starting at the node where they intersect and ending at both lists, so the latter list is essentially shared. We can also know that if the ends of the two lists are aligned, the ends of the two lists must be equal. So we can solve the problem as follows:
- You want a linked list to walk through and record its length
- As we iterate over another list, n decreases by one each time we iterate
- After traversal, pointer cur1 points to the last node of head1, and pointer cur2 points to the last node of head2. = cur2 so the two lists don’t want to cross.
- At the end of the loop, we assume that hea1 is longer than head2, so n must be positive, which means that if we move the head pointer of Head1 to the right by n numbers, the length of the remaining list will be the same as that of head2
- Then point1 and point2 will go together so that the two points will always be equal, and the first equal point is the point where the two lists intersect.
private Node intersect(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while(cur1.next ! = null) { n++; cur1 = cur1.next; }while(cur2.next ! = null) { n--; cur2 = cur2.next; }if(cur1 ! = cur2) {returnnull; } // make cur1 point to the longer list and cur2 point to the shorter listif (n > 0) {
cur1 = head1;
cur2 = head2;
} else{ cur1 = head2; cur2 = head1; } n = Math.abs(n); // Longer lists take n steps firstwhile(n ! = 0) { cur1 = cur1.next; } // If two lists go together, the first equal node is the first node that intersectswhile(cur1 ! = cur2) { cur1 = cur1.next; cur2 = cur2.next; }return cur1;
}
Copy the codeconclusion
Some people say that the article is too long. I didn’t expect the article to get so long. Please also sit down to see, every time to the topic of their own sit down to do it again. After we all understand, I believe that we are almost fearless single – linked list of interview questions.
Welcome to pay attention to my personal blog address, the algorithm of this paper has also been uploaded to my Github. NodePractice and then I’m going to start with arrays and strings. I’m sure I’ll be seeing my long and smelly articles again soon.
Finally, may everything come to him who waits.