Java circular linked list
- Give you a head node of the linked list to judge whether there are links in the linked list.
- Returns true if there are links in the linked list. Otherwise, false is returned.
LeetCode's friends use the fast and slow double pointer writing method to judge... I don't think it's necessary. It's a little inefficient Let's see how I write
public boolean hasCycle(){
Node temp = head; //The initial node is the head node (a moving pointer to the currently traversed node)
while (temp.next != null){ //Traversal linked list
temp = temp.next;
if (temp == head){ //If the current node is equal to the head node, there is a ring
return true;
}
}
return false; //Exit before the loop is finished. while returns false
}
Let's look at the writing of fast and slow double pointers
public class Solution {
public boolean hasCycle(ListNode head) {
//Fast and slow pointers go from the same starting point
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next !=null){
fast =fast.next.next; //Come on, take two steps
slow = slow.next; //Slow the pointer one step
if(slow==fast){ //When the fast and slow pointers meet, they prove that there is a ring
return true;
}
}
//Otherwise, there is no ring
return false;
}
}
Author: nanasemalu
Link: https://leetcode-cn.com/leetbook/read/linked-list/jbex5/?discussion=nwnrlh
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.
Tested Under 100000 nodes, the execution time of my method is 4ms The execution time of the fast and slow double pointer method is 6ms
Under 1 million nodes, the execution time of my method is 7ms The execution time of the fast and slow double pointer method is 11ms
But LeetCode said that my code ran out of time, but it can run on my IDE and is faster than the double pointer method
Java to find the entry point of circular linked list
- Given a linked list, return the first node from the linked list into the ring. If the linked list is acyclic, null is returned.
I couldn't understand it at first. I read and write a little bit along with the code in the comment area. Later, I understood it after more research
(I always thought that the tail node of the ring linked list must be connected to the head node... In fact, the tail node can be connected to any node after the head...)
If it's just head to tail, there's no need to have a loop entry point, because the head is the loop entry point... I've been stuck here all the time
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if (slow == fast){
break;
}
}
if (fast == null || fast.next == null){
return null;
}
slow = head;
while (true){
if (slow == fast){
break;
}
slow = slow.next;
fast = fast.next;
}
return fast;
}
Java returns the intersection point of the intersecting linked list
- Here are the head nodes headA and headB of the two single linked lists. Please find and return the starting node where the two single linked lists intersect. If the two linked lists do not have intersecting nodes, null is returned.
public Node getIntersectionNode(Node nodeA,Node nodeB){
int nodeALength = length(nodeA);
int nodeBLength = length(nodeB);
Node tempA = nodeA;
Node tempB = nodeB;
if (nodeALength == nodeBLength){
while (tempA != null){
if (tempA == tempB){
return tempA;
}
tempA = tempA.next;
tempB = tempB.next;
}
}else {
if (nodeALength > nodeBLength){
int length = nodeALength - nodeBLength;
int i = 0;
while (i < length){
tempA = tempA.next;
i++;
}
while (tempA != null){
if (tempA == tempB){
return tempA;
}
tempA = tempA.next;
tempB = tempB.next;
}
}else {
int length = nodeBLength - nodeALength;
int i = 0;
while (i < length){
tempB = tempB.next;
i++;
}
while (tempA != null){
System.out.println(tempA);
System.out.println(tempB);
if (tempA == tempB){
return tempA;
}
tempA = tempA.next;
tempB = tempB.next;
}
}
}
return null;
}
public int length(Node node) {
int length=0;
Node temp = node;
while(temp.next != null){
length++;
temp = temp.next;
}
return length;
}
Very satisfied with the writing~Execution time exceeds 99.98%,Memory consumption exceeds 87.76%
Delete the penultimate node of the linked list
- Give you a linked list, delete the penultimate node of the linked list, and return the head node of the linked list.
public int length(ListNode node) {
int length=0;
ListNode temp = node;
while(temp.next != null){
length++;
temp = temp.next;
}
return length;
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode temp = head;
if (head.next == null){
return null;
}
int length = length(head) - n;
int i = 0;
if (length == -1){
head = head.next;
return head;
}
while (temp != null){
if (i == length){
temp.next = temp.next.next;
}
i++;
temp = temp.next;
}
return head;
}
Very satisfied with the writing~Execution time exceeds 100%,Memory consumption exceeds 87.10%
Java reverse linked list
- Give you the head node of the single linked list. Please reverse the linked list and return the reversed linked list.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public ListNode reverseList(ListNode head) {
if (head == null){
return null;
}
ListNode temp = head;
ListNode nowHead = head; //Current header node
while (temp.next != null){
ListNode next = temp.next.next; //Get the second bit after 1 first: 1-2-3-4-5 val (3-4-5) second: 2-1-3-4-5 val (4-5)
temp.next.next = nowHead; //Put the last number of 1 in front of the header node first: 2-1 second: 3-2-1
nowHead = temp.next; //The number after the current header node is 1
temp.next = next; //1 is modified to the last two digits of the original 1 first: 2-1-3-4-5 second: 3-2-1-4-5 and so on
}
return nowHead;
}
Execution time exceeds 100%，Occupy more than 98% memory.54% ...When you write, your mind is clear. When you finish writing, your head is covered. When you write notes, you put them in your head whil Run it again, ha ha, human brain computer
Remove 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's node and returns a new header node.
public ListNode removeElements(ListNode head, int val) {
ListNode temp = head;
while (temp.val == val){
temp = temp.next;
if (temp == null){
return null;
}
}
while (temp != null){
if (temp.next.val == val){
temp.next = temp.next.next;
}
temp = temp.next;
}
return head;
}
No problem with the code. LeetCode didn't give it. Let's look at the writing of recursion
public Node recursion(Node node,int val){
if (node == null){ //Recursion to the last one returns null
return null;
}
node.next = recursion(node.next,val); //The next of the current node is the return value of the next of the current node (when recursing to the last node, recursion will return Return to null, and the next of the current node (currently the last node) is equal to null)
return node.data == val ? node.next : node; //If data == val, the next node of the current node will be returned; otherwise, the current node will be returned
}
Parity linked list
- Given a single linked list, all odd and even nodes are arranged together. Note that the odd and even nodes here refer to the parity of node numbers, not the parity of node values.
public ListNode oddEvenList(ListNode head) {
if (head == null){
return null;
}
ListNode headA = head;
ListNode headB = head.next;
while (headB != null && headB.next != null){
ListNode nextA = headB.next;
headB.next = headB.next.next;
nextA.next = headA.next;
headA.next = nextA;
headA = headA.next;
headB = headB.next;
}
return head;
}
Palindrome linked list
- Give you the head node of a single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return true; Otherwise, false is returned.
My idea is to reverse the linked list and compare it with the original table, but in this case, the linked list structure will be modified. The solution is to reverse the previous new class storage table
This is not only inefficient, but also changes the memory space. In short, it is not good (although it can also achieve results)
This problem was finally given up( Title website)