1. Delete all nodes in the linked list equal to the given value val.
If a node is no longer referred to by Java, it will be automatically deleted
The linked list is as follows:
The given value is assumed to be 3:
Reference code:
//Delete all nodes with the value of key
public void removeAllKey(int val){
if(this.head == null){//If there is no node, return directly
return;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while(cur!=null){//Node is not empty, enter loop
if(cur.val == val){//Find a node with the same value as the specified value and delete it
prev.next = cur.next;
cur = cur.next;//Move backward one bit after deletion
}else{//Different from the specified value, move one bit backward
prev = cur;
cur = cur.next;
}
}
//Finally, judge whether the header node is the value
if(this.head.val == val){
this.head = this.head.next;
}
}
2. Reverse a single linked list.
Inverting refers to inverting the node, not inverting the value of the node
Before reversing:
After reversal:
Note: the next field of the single chain tail node is null
Reference code:
//Reverse a single linked list
public ListNode reverseList(){
//If there is no node or only one node, return directly
if(head == null||head.next == null){
return head;
}
ListNode cur = head;
ListNode newHead = null;
while(cur!=null){
ListNode curNext = cur.next;//Leave curNext for backward movement
cur.next = newHead;//Set the next field of this node as newHead
newHead = cur;//The newHead node moves back one bit
cur = curNext;//cur moves back one bit
}
return newHead;
}
3. Given a non empty single linked list with head node, return the intermediate node of the linked list. If there are two intermediate nodes, the second intermediate node is returned.
The fast and slow pointer method is adopted. For each step of the slow pointer, the fast pointer takes two steps. When the fast pointer reaches the end, the slow pointer reaches the middle node
At the beginning, both the fast pointer and the slow pointer are in the header node
Last position
Reference code:
//Given a non empty single linked list of the leading node, return the intermediate node of the linked list
public ListNode middleNode(){
if(head == null) return head;
ListNode fast = head;//Quick pointer
ListNode slow = head;//Slow pointer
while(fast!=null && fast.next!=null){
fast = fast.next.next;//Take two steps
slow = slow.next;//Take a step
}
return slow;//Return slow pointer
}
4. Input a linked list and output the penultimate node in the linked list.
The fast and slow pointer method is adopted. The fast pointer takes k-1 steps first, and then the fast pointer and slow pointer move forward synchronously until the fast pointer reaches the end
The following linked list assumes that k is 2, and the starting position of its speed pointer is:
The final result is:
Reference code:
//Input a linked list and output the penultimate node in the linked list
//First let the fast pointer go k-1 steps, and then let the fast pointer and the slow pointer go synchronously
public ListNode findKthToTail(int k){
if(head == null) return null;//Empty node
if(k<0){//Illegal coordinates
return null;
}
ListNode fast = head;
ListNode slow = head;
while(k-1 != 0){//Handle cases where k may be greater than the length of the linked list
if(fast.next != null){
fast = fast.next;
k--;
}else{
return null;
}
}
while(fast.next != null){//Fast and slow pointer synchronization
fast = fast.next;
slow = slow.next;
}
return slow;
}
5. Merge the two ordered linked lists into a new ordered linked list and return. The new linked list is composed of all nodes of a given two linked lists.
There are two ordered linked lists:
After the splicing is completed:
Reference code:
//Merge the two ordered linked lists into a new ordered linked list and return
public ListNode mergeTowList(ListNode headA,ListNode headB){
if(headA == null) return headB;
if(headB == null) return headA;
if(headA == null && headB == null) return null;
ListNode newHead = new ListNode(-1);//Apply for a head node, puppet node
ListNode tmp = newHead;//Move tmp and keep newHead position
while(headA != null && headB != null){//Connect who is small first until one of them reaches the tail node
if(headA.val<headB.val){//Link headA
tmp.next = headA;
headA = headA.next;
}else{
tmp.next = headB;//Link headB
headB = headB.next;
}
tmp = tmp.next;//Move back one bit after connecting
}
if(headA == null){//Head a first to tail node
tmp.next = headB;
}
if(headB == null){//headB first to tail node
tmp.next = headA;
}
return newHead.next;//Returns the next node of the puppet node
}
6. Write code to divide the linked list into two parts based on the given value X. all nodes less than X are arranged before nodes greater than or equal to x, and the order is guaranteed to remain unchanged.
It is assumed that there is the following linked list:
If the given value x is 6
Create two linked lists respectively. The former is less than X and the latter is greater than x. In order to keep the order unchanged, the tail interpolation method should be used
Reference code:
//The linked list is divided into two parts based on the given value x, and all nodes less than X are arranged before nodes greater than or equal to X
public ListNode partition(int x){
ListNode cur = this.head;//Used to traverse the specified linked list
ListNode bs = null;//Start of the previous linked list
ListNode be = null;//The end of the previous linked list
ListNode as = null;//The start of the next linked list
ListNode ae = null;//The end of the last linked list
while(cur != null) {//Tail interpolation is used to ensure that the order remains unchanged
if (cur.val < x) {
if (bs == null) { //Part I first insertion
bs = cur;
be = cur;
} else {//Multiple inserted connections
be.next = cur;
be = be.next;
}
} else {
if (as == null) {//Part II first insertion
as = cur;
ae = cur;
} else {//Multiple inserted connections
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;//Specify the traversal position of the linked list to move back one bit
}
if(bs == null){//If all values are greater than x
return as;
}
//bs!=null
be.next = as;//be is not empty. The node must have data. Connect it with the next linked list
if(as != null){//If as is not empty, set the next field of the tail node of the linked list to empty
ae.next = null;
}
return bs;
}
7. In a sorted linked list, there are duplicate nodes. Please delete the duplicate nodes in the linked list. The duplicate nodes are not retained and the chain header pointer is returned.
Suppose the following linked list is given:
After deleting the duplicate node, it is:
Reference code:
//Delete the duplicate nodes in an ordered linked list. The duplicate nodes are not retained and the chain header pointer is returned
public ListNode deleteDuplication(){
ListNode newHead = new ListNode(-1);//Apply for a puppet node
ListNode tmp = newHead;//Move tmp to ensure that the puppet node position does not move
ListNode cur = this.head;
while(cur != null){
//cur.next!=null; Judge whether there is only one node or tail node
if(cur.next != null && cur.val == cur.next.val){
//In the process of cur walking again, it is possible that the rest are the same
while(cur.next != null && cur.val == cur.next.val){
cur = cur.next;
}
cur = cur.next;//If the cycle is not satisfied, take a step back
}else{//Tail interpolation
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
tmp.next = null;//Set manually to prevent the last node from being repeated
return newHead.next;
}
8. Judge whether the linked list has palindrome structure
Example of palindrome structure:
method:
-
First, find the middle node of the linked list through the fast and slow pointer method
-
Reverse the linked list from the intermediate node
-
The head and slow pointers match from head to tail until the two pointers collide. In case of inconsistency, they directly return false, otherwise they return true
Note: distinguish between odd and even numbers. When even numbers match, compare them one more step
Reference code:
//Check the palindrome structure of the linked list, for example: 12321
public boolean chkPalindrome() {
if (this.head == null) {
//Not a single node
return true;
}
if (this.head.next == null) {
//Only one node
return true;
}
//1 find intermediate nodes
ListNode slow = this.head;
ListNode fast = this.head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
//The node pointed to by slow is the intermediate node
//2. Flip
ListNode cur = slow.next;
while (cur != null) {
ListNode curNext = cur.next;//Keep cur next
cur.next = slow;
slow = cur;
cur = curNext;
}
//After inversion, slow refers to the last node
while (slow != head) {
if (slow.val != head.val) {
return false;
}
if (head.next == slow) {//Even case
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
9. Enter two linked lists and find their first common node
The intersecting linked list has Y-type and X-type
The following is a linked list with common nodes:
method:
- First, get the length of the two linked lists respectively, and calculate the difference x
- Let the long linked list Go x steps first, and then let the two linked lists go while matching the value until the end
Reference code:
//Enter two linked lists and find their first common node
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null) {
return null;
}
if(headB == null) {
return null;
}
int lenA = 0;
int lenB = 0;
//pl: represents the length of the long list, ps: represents the length of the short list
ListNode pl = headA;
ListNode ps = headB;
while(pl != null) {
lenA++;
pl = pl.next;
}
while(ps != null) {
lenB++;
ps = ps.next;
}
//The calculated length pl and ps are null, and the header node needs to be returned
pl = headA;
ps = headB;
/*
lenA And lenB results:
lenA > lenB
lenA == lenB
lenA < lenB
*/
int len = lenA-lenB;//Difference between two linked lists
// < 0 == 0 > 0
if(len < 0) {
pl = headB;
ps = headA;
len = lenB-lenA;
}
//Results: pl always points to the long list, ps always points to the short list, and len is always a positive number
while (len != 0) {
pl = pl.next;
len--;
}
while (pl != ps) {//Determine whether there is an intersection between two linked lists
pl = pl.next;
ps = ps.next;
}
//Can not write, assuming that there is no intersection, it is also null
if(pl == null ) {
return null;
}
return pl;
}
10. Given a linked list, judge whether there are links in the linked list
The linked list with links is as follows:
Specific form: linked list:
Methods: adopt the fast and slow pointer method. Each step of the slow pointer and two steps of the fast pointer will meet if there are links in the list
Reference code:
//Judge whether there are links in the linked list
public boolean hasCycle(){
ListNode fast = this.head;
ListNode slow = this.head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){
break;
}
}
if(fast == null || fast.next == null){
return false;
}
return true;
}
11. Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned
The fast and slow pointer method is adopted, and the speed of the fast pointer is twice that of the slow pointer
Assumptions:
Derivation of encounter formula:
Since each circle returns to the origin, it is finally equivalent to L=X
Reference code:
//Given a linked list, return the first node of the linked list into the ring. If the linked list has no ring, return null
public ListNode detectCycle(){
ListNode fast = this.head;
ListNode slow = this.head;
while(fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(slow == fast){//First meeting
break;
}
}
if(fast == null || fast.next == null){//No ring
return null;
}
//slow and fast met
slow = this.head;//slow starts from the starting position and fast starts from the meeting point
while(fast!=slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}