Examples
1. Reverse linked list (recursive, double pointer / iteration)
From LeetCode206
Supplement:
* 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; }
* }solution
1. Recursion
In recursive articles.
2. Double pointer
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode temp = null;
while(cur!=null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}cur points to the current node, pre points to the previous node, and temp points to the next node. Iteration.
Understanding (not guaranteed to be correct)
1. The linked list problem should draw the process in the book, so it is easy to get the algorithm.
2. Fixed position reverse linked list (recursive, double pointer / iteration)
From LeetCode92
Supplement:
* 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; }
* }solution
1. Double pointer solution
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if(left == right)
return head;
ListNode cur = head;
ListNode pre = null;
ListNode temp = null;
ListNode now = null;
ListNode r = null;
ListNode l = head;
int count = 1;
for(;count<left;count++){
cur = cur.next;
}
while(count<=right&&cur!=null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
count++;
}
for(int i =1;i<left-1;i++){
l=l.next;
}
if(left!=1){
l.next = pre;
pre = l;
}
now = head;
while(now.next!=null)
now = now.next;
now.next = temp;
if(left==1)
return pre;
return head;
}
}Write according to the double pointer algorithm of reverse linked list 1.
It is too violent to handle the linked list that has not been reversed (before left).
Big man's double pointer solution:
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// Define a dumpyhead to facilitate processing
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// Initialization pointer
ListNode g = dummyHead;
ListNode p = dummyHead.next;
// Move the pointer to the corresponding position
for(int step = 0; step < m - 1; step++) {
g = g.next; p = p.next;
}
// Insert node by head inserting method
for (int i = 0; i < n - m; i++) {
ListNode removed = p.next;
p.next = p.next.next;
removed.next = g.next;
g.next = removed;
}
return dummyHead.next;
}
}The dummy header pointer dummyHead is used to avoid the front and back boundary problems.
2. Iteration
Write when you have time.
Understanding (not guaranteed to be correct)
1. There are left and right boundary value problems in linked list problems. Introducing a virtual head pointer can avoid a large number of problems.
3. Intersecting linked list
From leetcode 160
solution
1. Double pointer IQ question
In fact, I walk twice. I often use this idea
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA;
ListNode B = headB;
while(A!=B){
if(A==null)
A = headB;
else
A = A.next;
if(B==null)
B = headA;
else
B = B.next;
}
return A;
}
}understand
None.
3. String addition (large number addition)
From LeetCode 415
solution
class Solution {
public String addStrings(String num1, String num2) {
StringBuffer sb = new StringBuffer();
int add = 0;
int i = num1.length()-1;
int j = num2.length()-1;
while(i>=0||j>=0||add!=0){
int x = i >= 0? num1.charAt(i) - '0' : 0;
int y = j >= 0? num2.charAt(j) - '0' : 0;
int result = x + y + add;
if(result>=10)
add = 1;
else
add = 0;
sb.append(result%10);
i--;
j--;
}
sb.reverse();
return sb.toString();
}
}understand
1. Double pointers point to single digits, and then use StringBuffer for storage and addition
2. There are many boundary conditions, which need special care.
3. You need to master String/StringBuffer/StringBuilder.
4. Merge two ordered arrays
From LeetCode88
be careful: 1. We need to review the question. The question tells us that it is an ordered array (from small to large).
solution
1. nt solution
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m;
for(int j = 0;j<n;i++,j++){
nums1[i] = nums2[j];
}
Arrays.sort(nums1);
}
}Throw it in and sort it directly.
2. Forward double pointer
- Because the order has been arranged, the smallest comparison only needs to compare the top elements.
- You can think of double pointers here, but this method must create a new array with high space complexity.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] result = new int[m+n];
int i=0,j=0,r=0;
while(i<m||j<n){
if(i==m){
result[r] = nums2[j];
j++;
}
else if(j==n){
result[r] = nums1[i];
i++;
}
else if(nums1[i]<nums2[j]){
result[r] = nums1[i];
i++;
}
else{
result[r] = nums2[j];
j++;
}
r++;
}
for(int q = 0;q<m+n;q++){
nums1[q] = result[q];
}
}
}3. Reverse double pointer
- Inverse idea of forward double pointer
- If you don't want to create a new array, the original elements of nums1 may be overwritten with minimum coverage
- So we can think of using the maximum to cover the last element of nums1, because nums1 has a fixed length.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int r = m+n -1;
while(i>=0||j>=0){
if(i==-1){
nums1[r] = nums2[j];
j--;
}
else if(j==-1){
nums1[r] = nums1[i];
i--;
}
else if(nums1[i]>nums2[j]){
nums1[r] = nums1[i];
i--;
}
else{
nums1[r] = nums2[j];
j--;
}
r--;
}
}
}understand
1. Review the topic.
5. Binary tree traversal
In the article of algorithm (8).
Very important. Very important. Very important. Very important. Very important. Very important. Very important. Very important. Very important. Very important.