濮阳做网站的公司有哪些,大理市住房和城乡建设局网站,公司部门聚餐计入什么科目,沈阳做网站怎样收费目录 1. 反转链表#xff08;简单#xff09;
1.1. 题目描述
1.2. 解题思路
方法一#xff1a;迭代#xff08;推荐使用#xff09;
方法二#xff1a;递归#xff08;扩展思路#xff09;
方法三#xff1a;使用栈解决
方法四#xff1a;双链表求解
2. 链表内…目录 1. 反转链表简单
1.1. 题目描述
1.2. 解题思路
方法一迭代推荐使用
方法二递归扩展思路
方法三使用栈解决
方法四双链表求解
2. 链表内指定区间反转中等
2.1. 题目描述
2.2. 解题思路
方法一头插法迭代推荐使用
方法二递归扩展思路
3. 链表中的节点每k个一组翻转中等
3.1. 题目描述
3.2. 解题思路
方法一递归推荐使用
方法二模拟法
4. 排序链表中等
4.1. 题目描述
4.2. 解题思路
方法一自顶向下归并排序
方法二自底向上归并排序
5. 合并两个排序的链表简单
5.1. 题目描述
5.2. 解题思路
方法一双指针迭代推荐使用
方法二双指针递归扩展思路
6. 合并k个已排序的链表较难
6.1. 题目描述
6.2. 解题思路
方法一归并排序思想推荐使用
方法二优先队列扩展思路
7. 判断链表中是否有环简单
7.1. 题目描述
7.2. 解题思路
方法双指针推荐使用
8. 链表中环的入口结点中等
8.1. 题目描述
8.2. 解题思路
方法双指针推荐使用
9. 相交链表简单
9.1. 题目描述
9.2. 解题思路
方法一哈希集合
方法二双指针
10. 环形链表II中等
10.1. 题目描述
10.2. 解题思路
方法一哈希表
方法二快慢指针
11. 链表中倒数最后k个结点简单
11.1. 题目描述
11.2. 解题思路
方法一快慢双指针推荐使用
方法二先找长度再找最后k扩展思路
12. 两个链表的第一个公共结点简单
12.1. 题目描述
12.2. 解题思路
方法双指针
13. 链表相加(二)中等
13.1. 题目描述
13.2 解题思路
方法反转链表法推荐使用
14. 两数相加中等
14.1. 题目描述
14.2. 解题思路
方法一模拟法
15. 单链表的排序中等
15.1. 题目描述
15.2. 解题思路
方法一归并排序推荐使用
方法二转化为数组排序扩展思路
16. 判断一个链表是否为回文结构简单
16.1. 题目描述
16.2. 解题思路
方法一数组复制反转法前置知识
方法二数组复制双指针前置知识
方法三长度法找中点推荐使用
方法四双指针找中点推荐使用
方法五栈逆序扩展思路
17. 链表的奇偶重排中等
17.1. 题目描述
17.2. 解题思路
方法双指针推荐使用
18. 删除有序链表中重复的元素-I简单
18.1. 题目描述
18.2. 解题思路
方法遍历删除推荐使用
19. 删除有序链表中重复的元素-II中等
19.1. 题目描述
19.2. 解题思路
方法一直接比较删除推荐使用
方法二哈希表扩展思路
20. 删除链表的中间节点中等
20.1. 题目描述
20.2. 解题思路
方法一快慢指针
21. 删除链表的倒数第n个节点中等
21.1. 题目描述
21.2. 解题思路
方法一双指针推荐使用
方法二长度统计法思路扩展
22. 从尾到头打印链表简单
22.1. 题目描述
22.2. 解题思路
23. 两两交换链表中的节点中等
23.1. 题目描述
23.2. 解题思路
方法一递归
方法二迭代
24. 复制带随机指针的链表中等
24.1. 题目描述
24.2. 解题思路
方法一回溯 哈希表
方法二迭代 节点拆分
25. 链表最大孪生和中等
25.1. 题目描述
25.2. 解题思路
快慢指针 翻转链表(头部翻转) 1. 反转链表简单 1.1. 题目描述 1.2. 解题思路
方法一迭代推荐使用 public class Solution {public ListNode ReverseList(ListNode head) {//处理空链表if(head null) return null;ListNode cur head;ListNode pre null;while(cur ! null){//断开链表要记录后续一个ListNode temp cur.next; //当前的next指向前一个cur.next pre; //前一个更新为当前pre cur; //当前更新为刚刚记录的后一个cur temp; }return pre;}
} 方法二递归扩展思路 public class Solution {public ListNode ReverseList(ListNode head) {//递归结束条件if(head null || head.next null)return head;//反转下一个ListNode newHead ReverseList(head.next); //逆转本级节点head.next.next head; //尾部设置空节点head.next null; return newHead;}
} 方法三使用栈解决 import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {StackListNode stack new Stack();//把链表节点全部摘掉放到栈中while (head ! null) {stack.push(head);head head.next;}if (stack.isEmpty())return null;ListNode node stack.pop();ListNode dummy node;//栈中的结点全部出栈然后重新连成一个新的链表while (!stack.isEmpty()) {ListNode tempNode stack.pop();node.next tempNode;node node.next;}//最后一个结点就是反转前的头结点一定要让他的next//等于空否则会构成环node.next null;return dummy;
}
}
方法四双链表求解 public ListNode ReverseList(ListNode head) {//新链表ListNode newHead null;while (head ! null) {//先保存访问的节点的下一个节点保存起来//留着下一步访问的ListNode temp head.next;//每次访问的原链表节点都会成为新链表的头结点//其实就是把新链表挂到访问的原链表节点的//后面就行了head.next newHead;//更新新链表newHead head;//重新赋值继续访问head temp;}//返回新链表return newHead;
}
2. 链表内指定区间反转中等
2.1. 题目描述 2.2. 解题思路
方法一头插法迭代推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode reverseBetween (ListNode head, int m, int n) {//加个表头ListNode res new ListNode(-1); res.next head;//前序节点ListNode pre res; //当前节点ListNode cur head; //找到mfor(int i 1; i m; i){ pre cur;cur cur.next;}//从m反转到nfor(int i m; i n; i){ ListNode temp cur.next;cur.next temp.next;temp.next pre.next;pre.next temp;}//返回去掉表头return res.next; }
}方法二递归扩展思路 Java实现代码
import java.util.*;
public class Solution {ListNode temp null;public ListNode reverse(ListNode head, int n){//只颠倒第一个节点后续不管if(n 1){ temp head.next;return head;}//进入子问题ListNode node reverse(head.next, n - 1); //反转head.next.next head;//每个子问题反转后的尾拼接第n个位置后的节点head.next temp; return node;}public ListNode reverseBetween (ListNode head, int m, int n) {//从第一个节点开始if(m 1) return reverse(head, n);//缩减子问题ListNode node reverseBetween(head.next, m - 1, n - 1); //拼接已翻转head.next node;return head;}
}3. 链表中的节点每k个一组翻转中等
3.1. 题目描述 3.2. 解题思路
方法一递归推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode reverseKGroup (ListNode head, int k) {//找到每次翻转的尾部ListNode tail head;//遍历k次到尾部 for(int i 0; i k; i){ //如果不足k到了链表尾直接返回不翻转if(tail null) return head;tail tail.next; }//翻转时需要的前序和当前节点ListNode pre null; ListNode cur head;//在到达当前段尾节点前while(cur ! tail){ //翻转ListNode temp cur.next; cur.next pre;pre cur;cur temp;}//当前尾指向下一段要翻转的链表head.next reverseKGroup(tail, k); return pre;}
} 方法二模拟法 class Solution {public ListNode reverseKGroup(ListNode head, int k) {ListNode hair new ListNode(0);hair.next head;ListNode pre hair;while (head ! null) {ListNode tail pre;// 查看剩余部分长度是否大于等于 kfor (int i 0; i k; i) {tail tail.next;if (tail null) {return hair.next;}}ListNode nex tail.next;ListNode[] reverse myReverse(head, tail);head reverse[0];tail reverse[1];// 把子链表重新接回原链表pre.next head;tail.next nex;pre tail;head tail.next;}return hair.next;}public ListNode[] myReverse(ListNode head, ListNode tail) {ListNode prev tail.next;ListNode p head;while (prev ! tail) {ListNode nex p.next;p.next prev;prev p;p nex;}return new ListNode[]{tail, head};}
} 4. 排序链表中等
4.1. 题目描述 4.2. 解题思路
方法一自顶向下归并排序 class Solution {public ListNode sortList(ListNode head) {return sortList(head, null);}public ListNode sortList(ListNode head, ListNode tail) {if (head null) {return head;}if (head.next tail) {head.next null;return head;}ListNode slow head, fast head;while (fast ! tail) {slow slow.next;fast fast.next;if (fast ! tail) {fast fast.next;}}ListNode mid slow;ListNode list1 sortList(head, mid);ListNode list2 sortList(mid, tail);ListNode sorted merge(list1, list2);return sorted;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead new ListNode(0);ListNode temp dummyHead, temp1 head1, temp2 head2;while (temp1 ! null temp2 ! null) {if (temp1.val temp2.val) {temp.next temp1;temp1 temp1.next;} else {temp.next temp2;temp2 temp2.next;}temp temp.next;}if (temp1 ! null) {temp.next temp1;} else if (temp2 ! null) {temp.next temp2;}return dummyHead.next;}
} 方法二自底向上归并排序 class Solution {public ListNode sortList(ListNode head) {if (head null) {return head;}int length 0;ListNode node head;while (node ! null) {length;node node.next;}ListNode dummyHead new ListNode(0, head);for (int subLength 1; subLength length; subLength 1) {ListNode prev dummyHead, curr dummyHead.next;while (curr ! null) {ListNode head1 curr;for (int i 1; i subLength curr.next ! null; i) {curr curr.next;}ListNode head2 curr.next;curr.next null;curr head2;for (int i 1; i subLength curr ! null curr.next ! null; i) {curr curr.next;}ListNode next null;if (curr ! null) {next curr.next;curr.next null;}ListNode merged merge(head1, head2);prev.next merged;while (prev.next ! null) {prev prev.next;}curr next;}}return dummyHead.next;}public ListNode merge(ListNode head1, ListNode head2) {ListNode dummyHead new ListNode(0);ListNode temp dummyHead, temp1 head1, temp2 head2;while (temp1 ! null temp2 ! null) {if (temp1.val temp2.val) {temp.next temp1;temp1 temp1.next;} else {temp.next temp2;temp2 temp2.next;}temp temp.next;}if (temp1 ! null) {temp.next temp1;} else if (temp2 ! null) {temp.next temp2;}return dummyHead.next;}
} 5. 合并两个排序的链表简单
5.1. 题目描述 5.2. 解题思路
方法一双指针迭代推荐使用 Java实现代码
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//一个已经为空了直接返回另一个if(list1 null) return list2;if(list2 null)return list1;//加一个表头ListNode head new ListNode(0); ListNode cur head;//两个链表都要不为空while(list1 ! null list2 ! null){ //取较小值的节点if(list1.val list2.val){ cur.next list1;//只移动取值的指针list1 list1.next; }else{cur.next list2;//只移动取值的指针list2 list2.next; }//指针后移cur cur.next; }//哪个链表还有剩直接连在后面if(list1 ! null) cur.next list1;elsecur.next list2;//返回值去掉表头return head.next; }
} 方法二双指针递归扩展思路 Java实现代码
public class Solution {public ListNode Merge(ListNode list1,ListNode list2) {//一个已经为空了返回另一个if(list1 null) return list2;if(list2 null)return list1;//先用较小的值的节点if(list1.val list2.val){ //递归往下list1.next Merge(list1.next, list2); return list1; }else{//递归往下list2.next Merge(list1, list2.next); return list2;}}
} 6. 合并k个已排序的链表较难
6.1. 题目描述 6.2. 解题思路
方法一归并排序思想推荐使用 图示 Java实现代码
import java.util.ArrayList;
public class Solution {//两个链表合并函数public ListNode Merge(ListNode list1, ListNode list2) { //一个已经为空了直接返回另一个if(list1 null) return list2;if(list2 null)return list1;//加一个表头ListNode head new ListNode(0); ListNode cur head;//两个链表都要不为空while(list1 ! null list2 ! null){ //取较小值的节点if(list1.val list2.val){ cur.next list1;//只移动取值的指针list1 list1.next; }else{cur.next list2;//只移动取值的指针list2 list2.next; }//指针后移cur cur.next; }//哪个链表还有剩直接连在后面if(list1 ! null) cur.next list1;elsecur.next list2;//返回值去掉表头return head.next; }//划分合并区间函数ListNode divideMerge(ArrayListListNode lists, int left, int right){ if(left right) return null;//中间一个的情况else if(left right) return lists.get(left);//从中间分成两段再将合并好的两段合并int mid (left right) / 2; return Merge(divideMerge(lists, left, mid), divideMerge(lists, mid 1, right));}public ListNode mergeKLists(ArrayListListNode lists) {//k个链表归并排序return divideMerge(lists, 0, lists.size() - 1);}
} 方法二优先队列扩展思路 Java实现代码
import java.util.*;
public class Solution {public ListNode mergeKLists(ArrayListListNode lists) {//小顶堆QueueListNode pq new PriorityQueue((v1, v2) - v1.val - v2.val); //遍历所有链表第一个元素for(int i 0; i lists.size(); i){ //不为空则加入小顶堆if(lists.get(i) ! null) pq.add(lists.get(i));}//加一个表头ListNode res new ListNode(-1); ListNode head res;//直到小顶堆为空while(!pq.isEmpty()){ //取出最小的元素ListNode temp pq.poll(); //连接head.next temp; head head.next;//每次取出链表的后一个元素加入小顶堆if(temp.next ! null) pq.add(temp.next);}//去掉表头return res.next; }
} 7. 判断链表中是否有环简单
7.1. 题目描述 7.2. 解题思路
方法双指针推荐使用 Java实现代码
public class Solution {public boolean hasCycle(ListNode head) {//先判断链表为空的情况if(head null) return false;//快慢双指针ListNode fast head; ListNode slow head;//如果没环快指针会先到链表尾while(fast ! null fast.next ! null){ //快指针移动两步fast fast.next.next; //慢指针移动一步slow slow.next; //相遇则有环if(fast slow) return true;}//到末尾则没有环return false; }
} 8. 链表中环的入口结点中等
8.1. 题目描述 8.2. 解题思路
方法双指针推荐使用 Java实现代码
public class Solution {//判断有没有环返回相遇的地方public ListNode hasCycle(ListNode head) {//先判断链表为空的情况if(head null) return null;//快慢双指针ListNode fast head; ListNode slow head;//如果没环快指针会先到链表尾while(fast ! null fast.next ! null){ //快指针移动两步fast fast.next.next; //慢指针移动一步slow slow.next; //相遇则有环返回相遇的位置if(fast slow) return slow;}//到末尾说明没有环返回nullreturn null; }public ListNode EntryNodeOfLoop(ListNode pHead) {ListNode slow hasCycle(pHead);//没有环if(slow null) return null;//快指针回到表头ListNode fast pHead; //再次相遇即是环入口while(fast ! slow){ fast fast.next;slow slow.next;}return slow;}
} 9. 相交链表简单
9.1. 题目描述 9.2. 解题思路
方法一哈希集合 public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {SetListNode visited new HashSetListNode();ListNode temp headA;while (temp ! null) {visited.add(temp);temp temp.next;}temp headB;while (temp ! null) {if (visited.contains(temp)) {return temp;}temp temp.next;}return null;}
} 方法二双指针 public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA null || headB null) {return null;}ListNode pA headA, pB headB;while (pA ! pB) {pA pA null ? headB : pA.next;pB pB null ? headA : pB.next;}return pA;}
} 10. 环形链表II中等
10.1. 题目描述 10.2. 解题思路
方法一哈希表 public class Solution {public ListNode detectCycle(ListNode head) {ListNode pos head;SetListNode visited new HashSetListNode();while (pos ! null) {if (visited.contains(pos)) {return pos;} else {visited.add(pos);}pos pos.next;}return null;}
} 方法二快慢指针 public class Solution {public ListNode detectCycle(ListNode head) {if (head null) {return null;}ListNode slow head, fast head;while (fast ! null) {slow slow.next;if (fast.next ! null) {fast fast.next.next;} else {return null;}if (fast slow) {ListNode ptr head;while (ptr ! slow) {ptr ptr.next;slow slow.next;}return ptr;}}return null;}
} 11. 链表中倒数最后k个结点简单
11.1. 题目描述 11.2. 解题思路
方法一快慢双指针推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode FindKthToTail (ListNode pHead, int k) {int n 0;ListNode fast pHead; ListNode slow pHead;//快指针先行k步for(int i 0; i k; i){ if(fast ! null)fast fast.next;//达不到k步说明链表过短没有倒数kelse return slow null;}//快慢指针同步快指针先到底慢指针指向倒数第k个while(fast ! null){ fast fast.next;slow slow.next;}return slow;}
} 方法二先找长度再找最后k扩展思路 Java实现代码
import java.util.*;
public class Solution {public ListNode FindKthToTail (ListNode pHead, int k) {int n 0;ListNode p pHead;//遍历链表统计链表长度while(p ! null){n;p p.next;}//长度过小返回空链表if(n k) return null;p pHead;//遍历n-k次for(int i 0; i n - k; i) p p.next;return p;}
} 12. 两个链表的第一个公共结点简单
12.1. 题目描述 12.2. 解题思路
方法双指针 Java实现代码
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {ListNode l1 pHead1, l2 pHead2;while(l1 ! l2){l1 (l1null)?pHead2:l1.next;l2 (l2null)?pHead1:l2.next;}return l1;}
} 13. 链表相加(二)中等
13.1. 题目描述 13.2 解题思路
方法反转链表法推荐使用 Java实现代码
import java.util.*;
public class Solution {//反转链表public ListNode ReverseList(ListNode pHead) { if(pHead null)return null;ListNode cur pHead;ListNode pre null;while(cur ! null){//断开链表要记录后续一个ListNode temp cur.next;//当前的next指向前一个cur.next pre; //前一个更新为当前pre cur; //当前更新为刚刚记录的后一个cur temp; }return pre;}public ListNode addInList (ListNode head1, ListNode head2) {//任意一个链表为空返回另一个if(head1 null) return head2;if(head2 null)return head1;//反转两个链表head1 ReverseList(head1); head2 ReverseList(head2);//添加表头ListNode res new ListNode(-1); ListNode head res;//进位符号int carry 0; //只要某个链表还有或者进位还有while(head1 ! null || head2 ! null || carry ! 0){ //链表不为空则取其值int val1 head1 null ? 0 : head1.val; int val2 head2 null ? 0 : head2.val;//相加int temp val1 val2 carry; //获取进位carry temp / 10; temp % 10; //添加元素head.next new ListNode(temp); head head.next;//移动下一个if(head1 ! null) head1 head1.next;if(head2 ! null)head2 head2.next;}//结果反转回来return ReverseList(res.next); }
} 14. 两数相加中等
14.1. 题目描述 14.2. 解题思路
方法一模拟法 class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head null, tail null;int carry 0;while (l1 ! null || l2 ! null) {int n1 l1 ! null ? l1.val : 0;int n2 l2 ! null ? l2.val : 0;int sum n1 n2 carry;if (head null) {head tail new ListNode(sum % 10);} else {tail.next new ListNode(sum % 10);tail tail.next;}carry sum / 10;if (l1 ! null) {l1 l1.next;}if (l2 ! null) {l2 l2.next;}}if (carry 0) {tail.next new ListNode(carry);}return head;}
} 15. 单链表的排序中等
15.1. 题目描述 15.2. 解题思路
方法一归并排序推荐使用 Java实现代码
import java.util.*;
public class Solution {//合并两段有序链表ListNode merge(ListNode pHead1, ListNode pHead2) { //一个已经为空了直接返回另一个if(pHead1 null) return pHead2;if(pHead2 null)return pHead1;//加一个表头ListNode head new ListNode(0); ListNode cur head;//两个链表都要不为空while(pHead1 ! null pHead2 ! null){ //取较小值的节点if(pHead1.val pHead2.val){ cur.next pHead1;//只移动取值的指针pHead1 pHead1.next; }else{cur.next pHead2;//只移动取值的指针pHead2 pHead2.next; }//指针后移cur cur.next; }//哪个链表还有剩直接连在后面if(pHead1 ! null) cur.next pHead1;elsecur.next pHead2;//返回值去掉表头return head.next; }public ListNode sortInList (ListNode head) {//链表为空或者只有一个元素直接就是有序的if(head null || head.next null) return head;ListNode left head; ListNode mid head.next;ListNode right head.next.next;//右边的指针到达末尾时中间的指针指向该段链表的中间while(right ! null right.next ! null){ left left.next;mid mid.next;right right.next.next;}//左边指针指向左段的左右一个节点从这里断开left.next null; //分成两段排序合并排好序的两段return merge(sortInList(head), sortInList(mid)); }
} 方法二转化为数组排序扩展思路 import java.util.*;
public class Solution {public ListNode sortInList (ListNode head) {ArrayListInteger nums new ArrayList(); ListNode p head;//遍历链表将节点值加入数组while(p ! null){ nums.add(p.val);p p.next;}p head;//对数组元素排序Collections.sort(nums); //遍历数组for(int i 0; i nums.size(); i){ //将数组元素依次加入链表p.val nums.get(i); p p.next;}return head;}
} 16. 判断一个链表是否为回文结构简单
16.1. 题目描述 16.2. 解题思路
方法一数组复制反转法前置知识 Java实现代码
import java.util.*;
public class Solution {public boolean isPail (ListNode head) {ArrayListInteger nums new ArrayList();//将链表元素取出一次放入数组while(head ! null){ nums.add(head.val);head head.next;}ArrayListInteger temp new ArrayList();temp (ArrayListInteger) nums.clone();//准备一个数组承接翻转之后的数组Collections.reverse(temp); for(int i 0; i nums.size(); i){int x nums.get(i);int y temp.get(i);//正向遍历与反向遍历相同if(x ! y) return false;}return true;}
} 方法二数组复制双指针前置知识 Java实现代码
import java.util.*;
public class Solution {public boolean isPail (ListNode head) {ArrayListInteger nums new ArrayList();//将链表元素取出一次放入数组while(head ! null){ nums.add(head.val);head head.next;}//双指针指向首尾int left 0; int right nums.size() - 1;//分别从首尾遍历代表正序和逆序while(left right){ int x nums.get(left);int y nums.get(right);//如果不一致就是不为回文if(x ! y) return false;left;right--;}return true;}
} 方法三长度法找中点推荐使用 Java实现代码
import java.util.*;
public class Solution {//反转链表指针ListNode reverse(ListNode head) { //前序节点ListNode prev null; while(head ! null){//断开后序ListNode next head.next; //指向前序head.next prev; prev head;head next;}return prev;}public boolean isPail (ListNode head) {ListNode p head;int n 0;//找到链表长度while(p ! null){ n;p p.next; }//中点n n / 2; p head;//遍历到中点位置while(n 0){ p p.next;n--;}//中点处反转p reverse(p); ListNode q head;while(p ! null){//比较判断节点值是否相等if(p.val ! q.val) return false;p p.next;q q.next;}return true;}
} 方法四双指针找中点推荐使用 Java实现代码
import java.util.*;
public class Solution {//反转链表指针ListNode reverse(ListNode head) { //前序节点ListNode prev null; while(head ! null){//断开后序ListNode next head.next; //指向前序head.next prev; prev head;head next;}return prev;}public boolean isPail (ListNode head) {//空链表直接为回文if(head null) return true;//准备快慢双指针ListNode slow head; ListNode fast head;//双指针找中点while(fast ! null fast.next ! null){ slow slow.next;fast fast.next.next;}//中点处反转slow reverse(slow); fast head;while(slow ! null){ //比较判断节点值是否相等if(slow.val ! fast.val) return false;fast fast.next;slow slow.next;}return true;}
} 方法五栈逆序扩展思路 Java实现代码
import java.util.*;
public class Solution {public boolean isPail (ListNode head) {ListNode p head;StackInteger s new Stack();//辅助栈记录元素while(p ! null){ s.push(p.val);p p.next;}p head;//正序遍历链表从栈中弹出的内容是逆序的while(!s.isEmpty()){ //比较是否相同if(p.val ! s.pop()) return false;p p.next;}return true;}
} 17. 链表的奇偶重排中等
17.1. 题目描述 17.2. 解题思路
方法双指针推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode oddEvenList (ListNode head) {//如果链表为空不用重排if(head null) return head;//even开头指向第二个节点可能为空ListNode even head.next; //odd开头指向第一个节点ListNode odd head; //指向even开头ListNode evenhead even; while(even ! null even.next ! null){//odd连接even的后一个即奇数位odd.next even.next; //odd进入后一个奇数位odd odd.next; //even连接后一个奇数的后一位即偶数位even.next odd.next; //even进入后一个偶数位even even.next; } //even整体接在odd后面odd.next evenhead; return head;}
} 18. 删除有序链表中重复的元素-I简单
18.1. 题目描述 18.2. 解题思路
方法遍历删除推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head null) return null;//遍历指针ListNode cur head; //指针当前和下一位不为空while(cur ! null cur.next ! null){ //如果当前与下一位相等则忽略下一位if(cur.val cur.next.val) cur.next cur.next.next;//否则指针正常遍历else cur cur.next;}return head;}
} 19. 删除有序链表中重复的元素-II中等
19.1. 题目描述 19.2. 解题思路
方法一直接比较删除推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head null) return null;ListNode res new ListNode(0);//在链表前加一个表头res.next head; ListNode cur res;while(cur.next ! null cur.next.next ! null){ //遇到相邻两个节点值相同if(cur.next.val cur.next.next.val){ int temp cur.next.val;//将所有相同的都跳过while (cur.next ! null cur.next.val temp) cur.next cur.next.next;}else cur cur.next;}//返回时去掉表头return res.next; }
} 方法二哈希表扩展思路 Java实现代码
import java.util.*;
public class Solution {public ListNode deleteDuplicates (ListNode head) {//空链表if(head null) return null;MapInteger,Integer mp new HashMap();ListNode cur head;//遍历链表统计每个节点值出现的次数while(cur ! null){ if(mp.containsKey(cur.val))mp.put(cur.val, (int)mp.get(cur.val) 1);elsemp.put(cur.val,1);cur cur.next;}ListNode res new ListNode(0);//在链表前加一个表头res.next head; cur res;//再次遍历链表while(cur.next ! null){//如果节点值计数不为1 if(mp.get(cur.next.val) ! 1) //删去该节点cur.next cur.next.next; elsecur cur.next; }//去掉表头return res.next; }
} 20. 删除链表的中间节点中等
20.1. 题目描述 20.2. 解题思路
解题思路 使用 slow 记录慢指针fast 记录快指针。
当 fast 的再一次移动就结束时说明 slow 的再一次移动也将到达中间点
那么这个时候就可以直接用 slow.next slow.next.next 来去掉中间节点。
方法一快慢指针
class Solution {public ListNode deleteMiddle(ListNode head) {if (head null || head.next null) {return null;}ListNode slow head;ListNode fast head.next;while (fast.next ! null fast.next.next ! null) {slow slow.next;fast fast.next.next;}slow.next slow.next.next;return head;}
}
21. 删除链表的倒数第n个节点中等
21.1. 题目描述 21.2. 解题思路
方法一双指针推荐使用 Java实现代码
import java.util.*;
public class Solution {public ListNode removeNthFromEnd (ListNode head, int n) {//添加表头ListNode res new ListNode(-1); res.next head;//当前节点ListNode cur head; //前序节点ListNode pre res; ListNode fast head;//快指针先行n步while(n ! 0){ fast fast.next;n--;}//快慢指针同步快指针到达末尾慢指针就到了倒数第n个位置while(fast ! null){fast fast.next;pre cur;cur cur.next;}//删除该位置的节点pre.next cur.next; //返回去掉头return res.next; }
} 方法二长度统计法思路扩展 Java实现代码
import java.util.*;
public class Solution {public ListNode removeNthFromEnd (ListNode head, int n) {//记录链表长度int length 0; //添加表头ListNode res new ListNode(-1); res.next head;//当前节点ListNode cur head; //前序节点ListNode pre res; //找到链表长度while(cur ! null){ length;cur cur.next;}//回到头部cur head; //从头遍历找到倒数第n个位置for(int i 0; i length - n; i){ pre cur;cur cur.next;}//删去倒数第n个节点pre.next cur.next; //返回去掉头节点return res.next; }
} 22. 从尾到头打印链表简单
22.1. 题目描述 22.2. 解题思路
class Solution {public int[] reversePrint(ListNode head) {int count 0; //链表结点的个数ListNode p head;while(p ! null){ //统计链表中结点的个数count;p p.next;}int[] ans new int[count]; //创建一个和结点个数等大的数组p head;int index count - 1; //作为索引填充数组从后往前填充while(p ! null){ans[index] p.val;p p.next;index--;}return ans;}
} 23. 两两交换链表中的节点中等
23.1. 题目描述 23.2. 解题思路
方法一递归 class Solution {public ListNode swapPairs(ListNode head) {if (head null || head.next null) {return head;}ListNode newHead head.next;head.next swapPairs(newHead.next);newHead.next head;return newHead;}
} 方法二迭代 Java代码
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyHead new ListNode(0);dummyHead.next head;ListNode temp dummyHead;while (temp.next ! null temp.next.next ! null) {ListNode node1 temp.next;ListNode node2 temp.next.next;temp.next node2;node1.next node2.next;node2.next node1;temp node1;}return dummyHead.next;}
} 24. 复制带随机指针的链表中等
24.1. 题目描述 24.2. 解题思路
方法一回溯 哈希表 Java代码
class Solution {MapNode, Node cachedNode new HashMapNode, Node();public Node copyRandomList(Node head) {if (head null) {return null;}if (!cachedNode.containsKey(head)) {Node headNew new Node(head.val);cachedNode.put(head, headNew);headNew.next copyRandomList(head.next);headNew.random copyRandomList(head.random);}return cachedNode.get(head);}
} 方法二迭代 节点拆分 class Solution {public Node copyRandomList(Node head) {if (head null) {return null;}for (Node node head; node ! null; node node.next.next) {Node nodeNew new Node(node.val);nodeNew.next node.next;node.next nodeNew;}for (Node node head; node ! null; node node.next.next) {Node nodeNew node.next;nodeNew.random (node.random ! null) ? node.random.next : null;}Node headNew head.next;for (Node node head; node ! null; node node.next) {Node nodeNew node.next;node.next node.next.next;nodeNew.next (nodeNew.next ! null) ? nodeNew.next.next : null;}return headNew;}
} 25. 链表最大孪生和中等
25.1. 题目描述 25.2. 解题思路
快慢指针 翻转链表(头部翻转)
传统方法
先使用快慢指针找到中间节点 Using the Fast Slow pointers to Find the middle point翻转第二部分 Reverse the secondPart通过同时遍历第一部分与反转后的第二部分得出最大结果 Add the values and store the maximum value
具体代码如下
class Solution {public int pairSum(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;}ListNode prev reverse(slow);ListNode head1 head, head2 prev;int res 0;while (head2 ! null) {res Math.max(head1.val head2.val, res);head1 head1.next;head2 head2.next;}return res;}private ListNode reverse(ListNode head) {if (head null || head.next null) {return head;}ListNode curr head;ListNode prev null;while (curr ! null) {ListNode next curr.next;curr.next prev;prev curr;curr next;}return prev;}
}
对原有思路进行改进
可以在使用快慢指针时同时对第一部分前一半链表进行翻转操作 相较于原先 找到中间节点后翻转第二部分 更加简洁快速
具体代码如下
class Solution {public int pairSum(ListNode head) {ListNode fast head;ListNode slow head;ListNode prev null;while (fast ! null fast.next ! null) {fast fast.next.next;ListNode next slow.next;slow.next prev;prev slow;slow next;}int res 0;while (slow ! null) {res Math.max(res, prev.val slow.val);prv prev.next;slow slow.next;}return res;}}
