Tag Archives: The list

The reason why HashMap multithreads send out life and death loops

This article is a learning record of Vaccine: Java HashMap’s endless loop, welcome to discuss ~
Suppose the state of a cylinder to be expanded is as follows:
1->; 2-> Null
1 for the current thread to insert a new element of an array of e: 1 and the next element next:
when thread 2 completed the expansion, the pointer to the current status to 2 – & gt; 1-> NULL
Thread 1 continues:
rst (e:1,next:2)
n>arrel :1 ->; null

e=next=2;
next=e1.next=1;

> (e:2,next:1)
> 1-> null

e=next=1;
next=e1.next=null;

(e:1,next:null)
new barrel :1 ->; 2-> 1 is just 1 lt; -> 2

e=next=null;

cpu100%
7 using head insert, 1.8 using tail insert for capacity expansion.
1.7 using head insert, 1.8 using tail insert for capacity expansion.

Leetcode-234: palindrome linked list

Topic describes
Determine whether a linked list is a palindrome list.
// 1 2 nil
// 1 2 1 nil
// 1 2 2 1 nil
Thought analysis
The fast and slow pointer finds the midpoint of the linked list and splits the midpoint and reverses the tail list to compare whether the values of the head and tail list are equal in turn
Code implementation

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	fast := head.Next
	slow := head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	tail := reverse(slow.Next)
	slow.Next = nil

	for head != nil && tail != nil {
		if head.Val != tail.Val {
			return false
		}
		head = head.Next
		tail = tail.Next
	}
	return true
}

func reverse(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	var pre *ListNode
	for head != nil {
		temp := head.Next
		head.Next = pre
		pre = head
		head = temp
	}
	return pre
}

【Hackerrank】Reverse a doubly linked list

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty.
Input Format
You have to complete the Node* Reverse(Node* head) method which takes one argument – the head of the doubly linked list. You should NOT read any input from stdin/console.
Output Format
Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Then return the head node of the reversed list. Do NOT print anything to stdout/console.
Sample Input
NULL
NULL <– 2 <–> 4 <–> 6 –> NULL
Sample Output

NULL
NULL <-- 6 <--> 4 <--> 2 --> NULL

Explanation
1. Empty list, so nothing to do.
2. 2,4,6 become 6,4,2 o reversing in the given doubly linked list. 

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
struct Node
{
	int data;
	Node* next;
	Node* prev;
};/*
   Reverse a doubly linked list, input list may also be empty
   Node is defined as
   struct Node
   {
     int data;
     Node *next;
     Node *prev
   }
*/
Node* Reverse(Node* head)
{
    // Complete this function
    // Do not write the main method. 
    if(head == NULL || head->next == NULL)
        return head;
    Node *p = head;
    Node *q = head->next;
    if(q->next == NULL)
    {
        q->next = p;
        q->prev = NULL;
        p->next = NULL;
        p->prev = q;
        return q;
    }
    while(q->next != NULL)
    {
        if(p == head)
            p->next = NULL;
        Node *_next = q->next;
        q->next = p;
        p->prev = q;
        p = q;
        q = _next;
    }
    q->next = p;
    p->prev = q;
    q->prev = NULL;
    return q;
}Node* Insert(Node *head, int data)
{
	Node *temp = new Node();
	temp->data = data; temp->prev = NULL; temp->next = NULL;
	if(head == NULL) return temp;
	head->prev = temp;
	temp->next = head;
	return temp;
}
void Print(Node *head) {
	if(head == NULL) return;
	while(head->next != NULL){ cout<<head->data<<" "; head = head->next;}
	cout<<head->data<<" ";
	while(head->prev != NULL) { cout<<head->data<<" "; head = head->prev; }
	cout<<head->data<<"\n";
}
int main()
{
	int t; cin>>t;
	Node *head = NULL;
	while(t--) {
	   int n; cin>>n;
           head = NULL;
	   for(int i = 0;i<n;i++) {
		   int x; cin>>x;
		   head = Insert(head,x);
	   }
	   head = Reverse(head);
	   Print(head);
	}
}

206. Reverse Linked List [easy] (Python)

Topic link
https://leetcode.com/problems/reverse-linked-list/
The questions in the original

Reverse a singly linked list.

The title translation
Flip a one-way linked list
Thinking method
This topic is relatively basic, and there are many solutions to it, and there are also many solutions to AC. Here, only part of the ideas are sorted out for reference.
Thinking a
Using the stack structure, the contents of the linked list can be pushed onto the stack in turn, and then ejected from the stack in turn to construct the reverse order. The following code emulates the stack with ordinary arrays.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = head
        newList = []
        while p:
            newList.insert(0, p.val)
            p = p.next

        p = head
        for v in newList:
            p.val = v
            p = p.next
        return head

Idea 2
Similar to the idea of a stack, but directly in the original linked list operation, by iterating the node reorganization, the previous node moved to the back of the reorganized list. It’s actually an upside-down operation.
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = None
        while head:
            p = head
            head = head.next
            p.next = new_head
            new_head = p
        return new_head

Thought three
Recursion. Notice the termination condition
code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        p = head.next
        n = self.reverseList(p)

        head.next = None
        p.next = head
        return n

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/51306170