链表的分解

删除排序链表中的重复元素2（重复元素彻底删除）

链接

方法一：分解链表

/*** 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 {//1.分解链表 方式public ListNode deleteDuplicates(ListNode head) {ListNode uniqueDummy = new ListNode(101);ListNode repeatDummy = new ListNode(101);ListNode res=uniqueDummy;ListNode cur=head;//遍历原链表while(cur!=null){//cur节点是重复节点if(cur.next!=null && cur.val==cur.next.val || cur.val==repeatDummy.val){repeatDummy.next=cur;repeatDummy=repeatDummy.next;}else{//cur不是重复节点uniqueDummy.next=cur;uniqueDummy=uniqueDummy.next;}cur=cur.next;}uniqueDummy.next=null;return res.next;}
}

方式二：快慢指针

class Solution {//快慢指针方法，快指针探路 慢指针更新答案链表public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(101);dummy.next=head;ListNode slow=dummy;ListNode preFast=dummy;ListNode fast=head;while(fast!=null){if(fast.next!=null && fast.val!=preFast.val && fast.val!=fast.next.val){//fast节点不重复slow.next=fast;slow=slow.next;}if(fast.next==null && fast.val!=preFast.val){slow.next=fast;slow=slow.next;}fast=fast.next;preFast=preFast.next;}slow.next=null;return dummy.next;}
}

递归解法

/*** 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 {//递归解法//定义：给你一条头结点是head的链表 删除重复元素后返回头结点public ListNode deleteDuplicates(ListNode head) {//如果 只有一个节点 或者没有节点 就不用删除if(head==null || head.next==null){return head;}//如果head节点与后面的节点不同if(head.val!=head.next.val){head.next= deleteDuplicates(head.next);return head;}//如果head节点与后面的节点相同while(head.next!=null && head.val==head.next.val){head=head.next;}return deleteDuplicates(head.next);}
}

链表的合并

丑数2

链接

class Solution {public int nthUglyNumber(int n) {int p2=1,p3=1,p5=1;//指向ugly中的第一个丑数int val2=1,val3=1,val5=1;//表示三个链表的当前节点int p=1;//指向ugly的索引，便于更新uglyint[]ugly=new int[n+1];//ugly[i]:第i个丑数while(p<=n){//找出三个链表中当前节点的最小值int minVal=Math.min(Math.min(val2,val3),val5);ugly[p++]=minVal;//更新三个链表的当前节点if(minVal==val2){val2=2*ugly[p2++];}if(minVal==val3){val3=3*ugly[p3++];}if(minVal==val5){val5=5*ugly[p5++];}}return ugly[n];}
}

有序矩阵中第k小的元素

链接

class Solution {//用优先级队列辅助//思路：合并多条链表public int kthSmallest(int[][] matrix, int k) {//队列里存{matrix[i][j],i,j} 以便找到后面的元素PriorityQueue<int[]> pq=new PriorityQueue<int[]>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0]-o2[0];}});//maxtrix每一行相当于一条链表//先把各链表的头结点入队列for(int i=0;i<matrix.length;i++){pq.add(new int[]{matrix[i][0],i,0});}int res=0;while(!pq.isEmpty()&&k>0){int[] pollEle=pq.poll();res=pollEle[0];int i=pollEle[1],j=pollEle[2];//把(i,j+1)的元素入队列if(j+1<matrix[i].length){pq.add(new int[]{matrix[i][j+1],i,j+1});}k--;}return res;}
}

查找和最小的k对数字

链接

//优先级队列+合并链表
class Solution {public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {//队列里存{sum,i,j},sum是nums[i]+nums[j]PriorityQueue<int[]> pq=new PriorityQueue<int[]>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[0]-o2[0];}});int sz1=nums1.length;int sz2=nums2.length;//有sz1条链表，先把各链表的头结点入队列for(int i=0;i<sz1;i++){pq.add(new int[]{nums1[i]+nums2[0],i,0});}List<List<Integer>> res=new LinkedList<>();while(!pq.isEmpty()&&k>0){int[]pollEle=pq.poll();int i=pollEle[1];int j=pollEle[2];LinkedList<Integer> ele=new LinkedList();ele.add(nums1[i]);ele.add(nums2[j]);res.add(ele);//把[i,j+1]入队列if(j+1<nums2.length){pq.add(new int[]{nums1[i]+nums2[j+1],i,j+1});}k--;}return res;}
}

两数相加

链接

/*** 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 addTwoNumbers(ListNode l1, ListNode l2) {ListNode p1=l1;ListNode p2=l2;ListNode dummy=new ListNode(-1);ListNode p=dummy;int carry=0,add=0;while(p1!=null&&p2!=null){add=p1.val+p2.val+carry;carry=add/10;//进位的add%=10;ListNode newNode=new ListNode(add);p.next=newNode;p=p.next;p1=p1.next;p2=p2.next;}while(p1!=null){add=p1.val+carry;carry=add/10;add%=10;ListNode newNode=new ListNode(add);p.next=newNode;p=p.next;p1=p1.next;}while(p2!=null){add=p2.val+carry;carry=add/10;add%=10;ListNode newNode=new ListNode(add);p.next=newNode;p=p.next;p2=p2.next;}if(carry!=0){//还有进位ListNode newNode=new ListNode(carry);p.next=newNode;p=p.next;}p.next=null;return dummy.next;}
}

两数相加2

链接

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Stack<Integer> stack=new Stack();//翻转l1链表while(l1!=null){stack.add(l1.val);l1=l1.next;}ListNode head1= new ListNode(stack.pop());ListNode p1=head1;while(!stack.isEmpty()){int cur=stack.pop();ListNode newNode=new ListNode(cur);p1.next=newNode;p1=p1.next;}p1.next=null;//翻转l2链表while(l2!=null){stack.add(l2.val);l2=l2.next;}ListNode head2= new ListNode(stack.pop());ListNode p2=head2;while(!stack.isEmpty()){int cur=stack.pop();ListNode newNode=new ListNode(cur);p2.next=newNode;p2=p2.next;}p2.next=null;//开始计算 跟两数相加1一样的p1=head1;p2=head2;int add=0,carry=0;while(p1!=null && p2!=null){add=p1.val+p2.val+carry;carry=add/10;add%=10;stack.add(add);p1=p1.next;p2=p2.next;}while(p1!=null){add=p1.val+carry;carry=add/10;add%=10;stack.add(add);p1=p1.next;}while(p2!=null){add=p2.val+carry;carry=add/10;add%=10;stack.add(add);p2=p2.next;}if(carry!=0){stack.add(carry);}ListNode dummy=new ListNode(-1);ListNode p=dummy;while(!stack.isEmpty()){int cur=stack.pop();ListNode newNode=new ListNode(cur);p.next=newNode;p=p.next;}p.next=null;return dummy.next;}
}

回文单链表

回文链表

链接

方法一：用栈来辅助

/*** 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 boolean isPalindrome(ListNode head) {Stack<Integer> stack=new Stack();ListNode cur=head;while(cur!=null){stack.add(cur.val);cur=cur.next;}cur=head;while(cur!=null){int val=cur.val;int stackVal=stack.pop();if(val!=stackVal){return false;}cur=cur.next;}return true;}
}

方法二：快慢指针

/*** 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 boolean isPalindrome(ListNode head) {ListNode fast=head,slow=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}if(fast!=null){//奇数个 slow需要+1slow=slow.next;}//从①head->slow-1 ②fast->slowListNode head2= reverse(slow); while(head2!=null){if(head.val!=head2.val){return false;}head=head.next;head2=head2.next;}return true;}//返回翻转后的链表ListNode reverse(ListNode head){if(head==null){return null;}if(head.next==null){//一个节点return head;}ListNode pre=head;ListNode cur=head.next;pre.next=null;while(cur!=null){ListNode next=cur.next;cur.next=pre;pre=cur;cur=next;}return pre;}
}

迭代和递归翻转单链表

反转链表

方一：迭代

/*** 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 reverseList(ListNode head) {if(head==null){return null;}ListNode pre=head,cur=head.next;pre.next=null;while(cur!=null){ListNode next=cur.next;cur.next=pre;pre=cur;cur=next;}return pre;}
}

方二： 递归

/*** 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 {//递归翻转//定义：翻转以head为头结点的链表后并返回头结点public ListNode reverseList(ListNode head) {//只有一个节点或者是没有节点 不用翻转直接返回if(head==null||head.next==null){return head;}//翻转head.next链表 然后head接在他的后面ListNode realHead=reverseList(head.next);ListNode tail=head.next;tail.next=head;head.next=null;return realHead;}
}