1, Reversal of linked list (Leedcode.206 reverse linked list)
Reverse a linked list and define two pointers, one to replace the head node and the other to point to the next node. Then, instead of the pointer of the head node, go to the node that needs to be exchanged to carry out the operation similar to the head insertion method, and finally reverse the linked list.
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
ListNode cur = head;
ListNode curNext = cur.next;
head.next = null;
cur = curNext;
while (cur != null) {
curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}
}
2, Return the intermediate node of the linked list (the intermediate node of Leedcode.876 linked list)
If the linked list has an odd number of nodes, the intermediate node is returned
If the linked list has even nodes, the second node in the middle is returned
Idea: define the fast and slow pointer. The fast pointer walks two nodes at a time, the slow pointer walks one node at a time, and the odd node is fast Next equals null to end the loop. For even nodes, the slow pointer is the desired node after fast equals null to end the loop.
class Solution {
public ListNode middleNode(ListNode head) {
ListNode cur1=head;//Slow pointer
ListNode cur2=head;//Quick pointer
while(cur2!=null&&cur2.next!=null){//Odd and even nodes should be judged
cur1=cur1.next;
cur2=cur2.next.next;
}
return cur1;
}
}
3, Returns the penultimate node of the linked list
Solution: given a K value, return the penultimate node
1. First, judge whether K is legal. When the time complexity is low, you can't traverse one side of the linked list to compare the length of the linked list with K, and use a clever way to judge whether the fast pointer is equal to null to reduce the time complexity.
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(k<=0||head==null){
return null;
}
ListNode fast=head;//Define fast pointer
ListNode slow=head;//Define slow pointer
while(k-1!=0){
if(fast.next!=null){
fast=fast.next;
k--;
}else {//The validity of K value can be judged while traversing
System.out.println("You gave it K The value is too big");
return null;
}
}
while(fast.next!=null){
slow=slow.next;
fast=fast.next;
}
System.out.println(slow.val);
return slow;
}
}
4, Delete all nodes with the given value val in the linked list (Leetcode.203 removes linked list elements)
Give you a head node of the linked list and an integer val. please delete all nodes in the linked list that meet the requirements Val = = Val node and returns a new header node.
Solution: define a precursor node
public ListNode removeElements(ListNode head, int val) {
if(head==null)return null;
ListNode cur=head.next;
ListNode prev=head;
//Traverse each node of the single linked list
while (cur!=null){
if(cur.val==val){//This is the node you want to delete
prev.next=cur.next;//Assign the next address value to prev
cur=cur.next;
}else{//Not a deleted node
prev=prev.next;
cur=cur.next;
}
}if(head.val==val){//If the head node is also the node to be deleted
head=head.next;
}
return head;
}
5, Delete duplicate nodes in linked list
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. For example, the linked list 1 - > 2 - > 3 - > 3 - > 4 - > 4 - > 5 is 1 - > 2 - > 5 after processing
public class Solution {
public ListNode deleteDuplication(ListNode pHead){
ListNode tmpHead=new ListNode(-1);//Define puppet node
ListNode cur=pHead;
ListNode newHead=tmpHead;//Prevent the head node from being deleted
while (cur!=null){
if(cur.next!=null&&cur.val==cur.next.val){//Same value
while (cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
cur=cur.next;
}else {//
tmpHead.next=cur;
tmpHead=tmpHead.next;
cur=cur.next;
}
}
tmpHead.next=null;//Prevent the last node from being deleted
return newHead.next;
}
}
6, Split linked list given the value of X
For a certain value x, write a piece of code to rank all nodes less than x before other nodes, and cannot change the original data order, and return the head pointer of the rearranged linked list.
The problem solution defines the head pointer and tail pointer less than x, and defines the head pointer and tail pointer greater than x
After that, considering the special circumstances, if all nodes are greater than x, it will return as. If the last node is not greater than x, it will be placed in less than x, which will lead to Ae next!= Null, you need to set it to null;
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode bs=null;//The head of a node smaller than x
ListNode be=null;//The tail of a node smaller than x
ListNode as=null;//The head of a node larger than x
ListNode ae=null;//The tail of a node larger than x
ListNode cur=pHead;
while(cur!=null){
if(cur.val<x){//Values smaller than x cannot change the original order, so tail interpolation is used
if(bs==null){//First insertion
bs=cur;
be=cur;
}else {//Not first insertion
be.next=cur;
be=be.next;
}
}
else {//Value greater than x
if(as==null){//First insertion
as=cur;
ae=cur;
}else {//Not first insertion
ae.next=cur;
ae=ae.next;
}
}
cur=cur.next;
}
if(bs==null){//The first linked list has no data
return as;
}
be.next=as;
if(as!=null){//Prevent the last node next is not null
ae.next=null;
}
return bs;
}
}
7, Palindrome structure of linked list
The palindrome structure of the linked list is the same, for example, 1 2 3 2 1 Find the middle position of the linked list, and then reverse the second half of the linked list comparison (divided into parity node comparison)
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
if(head==null){return false;}
if(head.next==null){return true;}
ListNode fast=head;//Define the speed pointer to find the intermediate node
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNode cur=slow.next;//Find the intermediate node and reverse the linked list
while(cur!=null){//Reverse linked list
ListNode curNext=cur.next;
cur.next=slow;
slow=cur;
cur=curNext;
}
while(head!=slow){
if(head.val!=slow.val){
return false;
}
if(head.next==slow){
return true;
}
head=head.next;
slow=slow.next;
}
return true;
}
}
8, Judge whether the linked list has rings (Leedcode.141 circular linked list)
If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list. In order to represent the rings in a given linked list, we use the integer pos to represent the position where the tail of the linked list is connected to the linked list (the index starts from 0). If pos is - 1, there is no ring in the linked list. Note: pos is not passed as a parameter, but only to identify the actual situation of the linked list.
Returns true if there are links in the linked list. Otherwise, false is returned.
public boolean hasCycle(Node head){//Judge whether there is a link in the linked list. The address of the last node is the same as the address of the previous node. Whether the speed pointer meets or not. Two steps at a time is the fastest to find. Three or four steps are slow and may not meet. It is related to the size of the link
Node fast=this.head;
Node slow=this.head;
while(fast!=null&&fast.next!=null){//Judge whether there is a ring and then run
fast=fast.next.next;
slow=slow.next;
if(slow==fast){
return true;
}
}
return false;
}
