As the data stored in the computer data structure of one of two ways, data storage and chain store, sequential storage is commonly used array, the chain store is here we speak, the location of the sequential storage means that data stored in the memory is connected, the chain store also is continuous, so the chain store is to rely on what together! "Chain" is what we said just now, so what is the chain!
This chain is our definition, we can define a chain, a data associated with data in front of him, so that we can pass on a data along the chain to find the next data, singly linked lists, this is the data structure is singly linked lists as the name implies, we can only along the chain, once upon a time in the future, assuming that the data we are looking for in the list of the back, to find time will be very long, so we can use two chains connected data, data, in front of a chain to connect a chain connected at the back of the data, both to find before, can also find in the back, this is the double linked list,
We can create a linked list class,
public class ListNode {
Int var.
ListNode next;
ListNode (int x) {
This. Var=x;
}
ListNode () {
This. The var=0;
This. Next=null;
}
} this is one of the most simple singly linked list class, in this class, we use variables var stored data, adopt object next next object, The same we can also create a double linked list class
public class ListNode {
Int var.
ListNode prev.
ListNode next;
ListNode (int x) {
This. Var=x;
}
ListNode () {
This. The var=0;
This. Prev=null;
This. Next=null;
}
} this is the simplest a double linked list class, here we define two constructors, so we can allow you to create an empty list, in the same way, using variables var stored data, add the Object before a prev connections, of course, in the two linked list storage structure, we can completely var type for the Object, because of the type int data storage is too small, this can be set automatically according to the demand, List of the most basic properties has been created, you can define some commonly used methods,
We are the most commonly used method is print, insert, remove, replace,
List of traversal, the code is as follows:
public void print (ListNode l1) {
ListNode head=l1;
While (head. Next!=null) {
System. The out. Print (head. Var + "");
The head=head. The next;
}
{} public void remove (ListNode ListNode)
Listnode. Var=listnode. Next. Var;
Listnode. Next=listnode. Next, next;
} There are many ways, only wrote two kinds, in simple terms, the list of operations is actually a pointer changes, singly linked lists to modify a pointer and double linked list is need to modify the two Pointers, and can find the list of wanted by the operation time and method of space is relatively small, the reason is the reason why Pointers,
The following examples of Leetcode to deeply understand the list of
Easy
Incorporating two ascending list for ascending and linked list and returns a new, new linked list is given by joining together of two linked list of all nodes,
Example:
Input: 1 - & gt; 2-> 4, 1 - & gt; 3-> 4
Output: 1 - & gt; 1-> 2-> 3-> 4-> 4
Through number 318650 submission number 502, 3
Source: the power button (LeetCode)
Link: https://leetcode-cn.com/problems/merge-two-sorted-lists
Copyright belongs to the collar of the network, commercial reproduced please contact the official authorization, non-commercial reprint please indicate the source,
public ListNode mergerTwoLists (ListNode ListNode l1, l2) {
If (l1==null) {
Return l2;
} else if (l2==null) {
Return l1.
} else if (l1. Var & lt; L2. Var) {
L1. Next=mergerTwoLists (l1 and l2. Next);
Return l1.
} else {
L2. Next=mergerTwoLists (l2 and l1. Next);
Return l2;
}
} We adopted the approach of recursive, the answer is a pointer to constant transformation process, constantly judge small nodes, and then to transform of pointer, prone to think out the problem, each person is different, but the problem solving process, the process of problem solving is the official answer is simple, clear the problem is simple, easy to understand, can do it as a practice,
Given two (one-way) list, determine whether or not they intersect and returns the intersection point, please note that the definition of intersection based on the reference node, rather than based on the values of the nodes, in other words, if a list of the k node with another list of the first j a node is the same node (refer to the same), then the two list intersection,
Example 1:
Input: intersectVal=8, listA=,1,8,4,5 [4], by=,0,1,8,4,5 [5], skipA=2, skipB=3
Output: the Reference of the node with value=https://bbs.csdn.net/topics/8
Input: intersection node has A value of 8 (note that if the two list intersection is not 0), starting from its own header, the list for,1,8,4,5 [4], A linked list B for,0,1,8,4,5 [5], in A former two intersecting node; In B, before the intersection node has three nodes,
Source: the power button (LeetCode)
Link: https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
Copyright belongs to the collar of the network, commercial reproduced please contact the official authorization, non-commercial reprint please indicate the source,
public ListNode solution (ListNode head1, ListNode head2) {
If (head1==null | | head2==null) {
return null;
}
While (head1! Head2)={
Head1=head1==null? Head2: head1. Next;
Head2=head2==null? Head1: head2. Next;
}
Return head1;
} First saw this process is wrong, but self-study, found that writing is really NB, can see, the problem is simple, the most basic of violent solution is in the form of double pointer,