例题
1，反转链表（递归，双指针/迭代）
来自 LeetCode206
补充：
* 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; }
* }解法
1,递归
在递归文章里。
2，双指针
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指向当前节点，pre指向前一个节点，temp指向后一个节点。迭代进行。
理解（不保证正确）
1，链表题应该在本子上画出过程，这样很容易得到算法。
2，固定位置的反转链表（递归，双指针/迭代）
来自 LeetCode92
补充：
* 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; }
* }解法
1，双指针解法
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;
}
}根据反转链表1的双指针算法写出。
对前面未反转（left之前）的链表处理过于暴力。
大佬的双指针解法：
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// 定义一个dummyHead, 方便处理
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// 初始化指针
ListNode g = dummyHead;
ListNode p = dummyHead.next;
// 将指针移到相应的位置
for(int step = 0; step < m - 1; step++) {
g = g.next; p = p.next;
}
// 头插法插入节点
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;
}
}采用的是虚拟头指针dummyHead，这样可以避免前后边界问题。
2，迭代
有空写。
理解（不保证正确）
1，链表题中出现左右边界值问题，引入一个虚拟头指针，能避免大量问题。
3,相交链表
来自 LeetCode160
解法
1，双指针的智商题
其实就是走两次，经常能用到这个思想
/**
* 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;
}
}理解
无。
3，字符串相加（大数相加）
来自LeetCode 415
解法
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();
}
}理解
1，双指针指向个位数，然后用StringBuffer进行存储相加
2，边界条件很多，需要特别小心。
3，需要熟练掌握String/StringBuffer/StringBuilder。
4，合并两个有序数组
来自LeetCode88
注意：
1，需要审题，题目告诉我们是有序数组（从小到大）。
解法
1，nt解法
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);
}
}丢进去直接排序。
2，正向双指针
- 因为已经排好序，所以比较最小只需要比较最靠前的元素即可。
- 这里就能想到双指针，但是这个方法必须新建一个新数组，空间复杂度高。
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，反向双指针
- 正向双指针的逆想法
- 如果不想新建新数组的话，用最小覆盖可能会覆盖nums1原来的元素
- 所以我们可以想到用最大来覆盖，nums1最后的元素，因为nums1长度固定。
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--;
}
}
}理解
1，审题。
5，二叉树遍历
在算法(八)那篇文章里。
很重要。很重要。很重要。很重要。很重要。很重要。很重要。很重要。很重要。很重要。
正文完