Time: 2021.7.15-2021.7.19
1. LeetCode206 reverses the linked list
Traversing the list nodes in turn, each traversing a node is inverted one node
/** * Definition for singly-linked list. * public class ListNode { * int val; // Data domain * ListNode next; // * ListNode() {} * ListNode(int val) {this. val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }// The constructor *} */
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;// A pointer to the new list header node
ListNode cur = head;
while(cur ! =null) {
ListNode nextTemp = cur.next;/ / backup cur. Next
cur.next = pre;/ / update the cur. Next
pre = cur;/ / move the pre
cur = nextTemp;// Traverse the list
}
return pre;// Return the new list header node}}Copy the code2. LeetCode92 Reverse Linked List II
/** * 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; }} * * /
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
int len = right-left+1;// Count the number of nodes to be inverted
ListNode pre_head = null;// Initialize the precursors of the node to start inverting
ListNode result = head;// The final converted head node of the list, otherwise known as head
while(head! =null&& --left! =0) {// Move head forward left-1 position
pre_head = head;// Record the precursors of head
head = head.next;
}
ListNode modify_list_tail = head;// Set modify_list_tail to the current head, that is, the reversed end of the list
ListNode new_head = null;
while(head! =null&& len! =0) {// Invert len nodes
ListNode nextTemp = head.next;
head.next = new_head;
new_head = head;
head = nextTemp;
len--;
}
modify_list_tail.next = head;// Connect the inverted end of the list to the last node of the inverted segment
if(pre_head! =null) {// Not starting with the first node
pre_head.next = new_head;// Connect the front node of the inverted list to the head node of the inverted list
} else{
result = new_head;// The first node is inverted, and the result is the inverted head node
}
returnresult; }}Copy the code3. LeetCode160 intersecting linked list
1. Calculate the length of the headA and headB lists, and the length of the longer list
2. Move the pointer of the longer list to the position aligned with the pointer of the shorter list
3. HeadA and headB move at the same time. When the two Pointers point to the same node, it is found
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
int get_list_length(ListNode head){// Traverse the list to calculate the length of the list
int len = 0;
while(head ! =null){
len++;
head = head.next;
}
return len;
}
ListNode forward_long_list(int long_len,int short_len,ListNode head){
int delta = long_len-short_len;
while(head ! =null&& delta ! =0){
head = head.next;// Move the pointer forward by up to the point after the number of nodes
delta--;
}
return head;
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int list_A_len = get_list_length(headA);
int list_B_len = get_list_length(headB);// Find the length of two lists
if(list_A_len > list_B_len){
headA = forward_long_list(list_A_len,list_B_len,headA);// If list A is long, move headA to the corresponding location
}else{
headB = forward_long_list(list_B_len,list_A_len,headB);// If list B is long, move headB to the corresponding position
}
while(headA ! =null&&headB ! =null) {if(headA == headB){// When two Pointers point to the same node, it indicates that the node was found
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null; }}Copy the codeLeetCode antithesis
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/** Define two Pointers. In the first round, the two nodes that reach the end of the list point to the head of another list, and in the last round, if they meet, it is the intersection point. (In the first round, the length difference is erased.
if(headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
// In the first round, pA and pB move to the head of the other list when they first arrive at the end, and in the second round, if pA or pB intersect, they return the intersection point, and if they don't intersect, they end up with null==null
while(pA ! = pB) { pA = pA ==null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
returnpA; }}Copy the code4. LeetCode142 Circular Linked List II
Train of thought: fast and slow pointer race
The two Pointers have the same speed, and when they meet, they are the starting point of the ring
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; *} *} */
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
ListNode meet = null;// The node of the encounter
while(fast ! =null){
slow = slow.next;
fast = fast.next;// Slow and fast go first
if (fast == null) {
return null;// If fast encounters the tail of the list, null is returned
}
fast = fast.next;// Fast Take another step
if (fast == slow){
meet = fast;// Fast and slow meet, record the meeting position
break; }}if (meet == null) {
return null;// If they do not meet, then prove acyclic
}
while(fast ! =null&& meet ! =null) {
if(head == meet){// When they meet, indicate the starting position of the ring
return head;
}
head = head.next;// Head and meet one step at a time
meet = meet.next;
}
return null; }}Copy the code5. LeetCode86 separates linked lists
Use temporary head nodes
/** * 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; }} * * /
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode less_head = new ListNode(0);
ListNode more_head = new ListNode(0);// Set two temporary header nodes
ListNode less_ptr = less_head,more_ptr = more_head;// The corresponding pointer points to the two header nodes
while(head ! =null) {if(head.val < x){// If the value of the node is less than x, insert the node into the Less_ptr
less_ptr.next = head;
less_ptr = head;// After the link is complete, less_ptr moves backwards to point to head
}else{// Otherwise, insert the node into more_ptr
more_ptr.next = head;
more_ptr = head;
}
head = head.next;// Traverse the list
}
less_ptr.next = more_head.next;// Connect the less list tail to the more list head
more_ptr.next = null;// Set more_ptr (next) to null
return less_head.next;// The next node of less_head is the new list head node}}Copy the code6. LeetCode138 copies a linked list with random Pointers
Deep copy: the structure generates a completely new list, even if the original list is destroyed, the new list can be used independently
C++ : a Vector is a Sequence Container that encapsulates a dynamically sized array. Like any other type of container, it can hold objects of various types. It’s easy to think of a vector as a dynamic array that can hold any type.
/* // Definition for a Node. class Node { int val; Node next; Node random; Public Node(int val) {this.val = val; this.next = null; this.random = null; }} * /
class Solution {
public Node copyRandomList(Node head) {
HashMap<Node,Integer> node_map = new HashMap<>();// The map from the address to the node location
List<Node> node_vec = new ArrayList<>();// Use vector to access the address based on the storage node location
Node ptr = head;
int i = 0;
if(head==null) return null;
while(ptr ! =null) {// Push the new list node into node_vec to generate a map of the new list node location to the address
node_vec.add(new Node(ptr.val));
node_map.put(ptr,i);// Record the original list address to the node_map of the node location
ptr = ptr.next;// Iterate over the original list
i++;// I Record the location of the node
}
node_vec.get(0);
ptr = head;
i = 0;
while(ptr ! =null) {// Iterate through the original list again, connecting the next pointer and the random pointer of the new list
if(i+1>=node_vec.size()){
node_vec.get(i).next = null;
}else{
node_vec.get(i).next = node_vec.get(i+1);// Connect the new list next pointer
}
if(ptr.random ! =null) {int id = node_map.get(ptr.random);// Check with node_map
node_vec.get(i).random = node_vec.get(id);// The random pointer of the original linked list points to the id
}
ptr = ptr.next;// Connect the new list random pointer
i++;
}
return node_vec.get(0); }}Copy the codeLeetCode21 combines two ordered lists
Compare the nodes pointed to by L1 and L2, insert the smaller node into the pre pointer, and move the pointer of the smaller node forward.
/** * 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; }} * * /
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode temp_head = new ListNode(0);// Set temporary head node temp_head
ListNode pre = temp_head;// Use the pre pointer to point to temp_head
while(l1 ! =null&&l2 ! =null) {if(l1.val < l2.val){
pre.next = l1;
l1 = l1.next;
}else{
pre.next = l2;
l2 = l2.next;
}
pre = pre.next;// Pre points to the newly connected node
}
if(l1 ! =null){
pre.next = l1;
}
if(l2 ! =null){
pre.next = l2;
}
returntemp_head.next; }}Copy the code8. LeetCode23 merges K ascending lists
Train of thought: divide and conquer k linked list, two by two to merge
/** * 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; }} * * /
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length == 0)
return null;
if(lists.length == 1)
return lists[0];
if(lists.length == 2) {return mergeTwoLists(lists[0],lists[1]);
}
int mid = lists.length/2;
ListNode[] sub1_lists = new ListNode[mid];
ListNode[] sub2_lists = new ListNode[lists.length-mid];// Split lists into two sub-lists
for(int i = 0; i < mid; i++){
sub1_lists[i] = lists[i];
}
for(int i = mid,j = 0; i < lists.length; i++,j++){
sub2_lists[j] = lists[i];
}
return mergeTwoLists(mergeKLists(sub1_lists),mergeKLists(sub2_lists));// Divide and conquer
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = null;
if (l1.val <= l2.val){
head = l1;
head.next = mergeTwoLists(l1.next, l2);
} else {
head = l2;
head.next = mergeTwoLists(l1, l2.next);
}
returnhead; }}Copy the code