2021-8-6 复习链表
2021/8/6 23:36:29
本文主要是介绍2021-8-6 复习链表，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
链表算法题复习
- 链表题目列表
- 1 删除链表节点
- 2 反转链表
- 3 环形链表
- 4 合并链表
- 5 排序链表
链表题目列表
* 单链表实现 增 删 查 改 * 1.头结点不能动，所以需要辅助指针 * 我理解的误区是，整个temp.next改变的是temp，head没有变。实际应该temp只是一个指针 * 指向这根链表的某一个位置，修改的还是链表 * * 链表类题目主要有以下几种题型： * 删除链表节点 * 反转链表 * 合并链表 * 排序链表 * 环形链表
1 删除链表节点
package demo01.ListNode;
import java.util.HashSet;
/**
* 链表法一般都对应：指针法和递归法。
* 203.移除链表元素（剑指offer18），删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
* 面试题 02.01. 移除重复节点，移除未排序链表中的重复节点。保留最开始出现的节点。
* 82. 删除排序链表中的重复元素 II,已排序链表，删除所有重复元素
* 19. 删除倒数第 N 个节点
* 876. 链表的中间节点
* 86. 分割链表，把小于 x 的都放在前面，大的都放在后面
* 328. 奇偶链表
*
* @author:liuliping
* @date:2021/8/6 8:15
*/
public class deleteListNode {
// 1.所有满足val，可能删除头结点
public ListNode removeElements(ListNode head, int val) {
if(head==null) return head;
ListNode dummy = new ListNode(val-1,head);
// 2.指针删除节点,删除节点只需要一个指针
ListNode cur = dummy;
while(cur.next!=null){
if(cur.next.val == val) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}
// 递归法
public ListNode removeElements2(ListNode head, int val) {
if(head==null) return head;
head.next = removeElements2(head.next,val);
if(head.val==val) return head.next;
else return head;
}
public ListNode removeDuplicateNodes(ListNode head) {
// 未排序，重复，借助HashSet来判断第二次出现
if(head==null) return head;
HashSet<Integer> set = new HashSet<>();
ListNode cur = head;
// 头结点要先加入
set.add(cur.val);
while(cur.next!=null){
if(!set.add(cur.next.val)) cur.next = cur.next.next;
else cur = cur.next;
}
return head;
}
// 因为是已排序，所有相等的元素都是紧挨着，双指针找到所有重复首尾位置
public ListNode deleteDuplicates(ListNode head) {
if(head==null) return head;
ListNode dummy = new ListNode(head.val-1,head);
ListNode fast = dummy.next;
ListNode slow = dummy;
while(fast!=null && fast.next!=null){
// 确定重复元素的尾元素
if(fast.val==fast.next.val){
while(fast.next != null && fast.val == fast.next.val){
fast = fast.next;
}
slow.next = fast.next;
fast = fast.next;
}else{
slow = slow.next;
fast = fast.next;
}
}
return dummy.next;
}
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null) return head;
// 1.双指针，迈开步子
ListNode dummy = new ListNode(0,head);
ListNode fast = dummy.next;
ListNode slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while(fast!=null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
// 找位置的一般都是用到双指针
public ListNode middleNode(ListNode head) {
if(head==null) return head;
ListNode pre = head;
ListNode cur = head;
// 尤其注意这里，如果不判断 cur.next就会空指针异常
while(cur!=null && cur.next!=null){
pre = pre.next;
cur = cur.next.next;
}
return pre;
}
// 原地更新，快排的方式去前后交换：问题在于链表是单向的
// 所以只能选择额外空间存储新的顺序
public ListNode partition(ListNode head, int x) {
if(head==null) return head;
ListNode smallHead = new ListNode(0);
ListNode small = smallHead;
ListNode largeHead = new ListNode(0);
ListNode large = largeHead;
while(head!=null){
if(head.val<x){
small.next = head;
small = small.next;
}else{
large.next = head;
large = large.next;
}
head = head.next;
}
small.next = largeHead.next;
large.next = null;
return smallHead.next;
}
// 可以直接入分割链表一样操作，但是要充分利用到奇偶的特性，奇偶之间是前后相连的状态
// 前后指针，原地更新
public ListNode oddEvenList(ListNode head) {
if(head==null) return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while(even!=null && even.next!=null){
odd.next = even.next;
odd = odd.next;//因为本身 even就是odd后面一个元素，所以要先odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
}
2 反转链表
/**
*
* 反转类链表题目
* 剑指offer24、反转链表
* 92、 反转链表II ，反转left-right区间范围的链表
* 25、 k个一组反转链表
* 234、判断是否为回文链表
*
* @author sommer1111
* @date 2021/5/31 10:04
*/
public class all {
//指针法反转链表
public ListNode reverseList(ListNode head) {
if(head==null) return head;
ListNode pre = null;
ListNode cur = head;
while(cur!=null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
//递归法反转链表
public ListNode reverseList2(ListNode head) {
if(head==null) return head;
// 这一步递归就代表后面所有都反转好了，因为返回的是头结点
// 所以last就是原来的最后一个元素，反转之后的头结点
ListNode last = reverseList2(head.next);
//head.next原先是last，所以此时将last的next指向head，也就是反转最后一个头结点
head.next.next = head;
// 队尾指向null，完成反转
head.next = null;
return last;
}
// 指针法,三指针穿针引线
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head==null) return head;
// 可能会反转到头结点
ListNode dummy = new ListNode(0,head);
// 1.找到开始节点，注意节点从1开始数起
ListNode pre = dummy;
for (int i = 0; i < left-1; i++) {
pre = pre.next;//先找到反转开始的前一个元素
}
ListNode cur = pre.next;//真正反转的指针
// 2.反转操作，只需要操作指针即可
for (int i = 0; i < right-left; i++) {
ListNode temp = cur.next;
cur.next = temp.next;//cur——>翻转元素后一个未翻转元素
temp.next = pre.next;//将cur——>temp,变成temp——>cur
pre.next = temp;//pre——>cur,变成pre——>temp
}
return dummy.next;
}
// 凡涉及到这种规律性重复的均需要考虑到递归
public ListNode reverseKGroup(ListNode head, int k) {
if(head==null) return head;
ListNode cur = head;
// 1.找到第一组k的末尾元素，如果元素不够就直接返回
for (int i = 0; i < k; i++) {
if(cur==null) return head;
cur = cur.next;
}
// 2.反转第一组k个元素
ListNode newHead = reverse(head, cur);
// 3.原先pre指向头结点，所以反转之后pre指向了尾节点
head.next = reverseKGroup(cur, k);
return newHead;
}
// 注意这部分并没有反转到end这个值，只是当做了边界值来判断，所以上面是reverseKGroup(cur, k)
public ListNode reverse(ListNode begin,ListNode end){
ListNode pre = null;
ListNode cur = begin;
while(cur!=end){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
// 备注：改变了链表原来的位置，需要的话可以存储几个关键节点反转回去。
public boolean isPalindrome(ListNode head) {
// 思路，反转后半部分，双指针遍历比较是否一致
if(head==null) return true;
// 1.找到中间的元素，但是需要奇偶情况记录
ListNode pre = head;
ListNode cur = head;
while(cur!=null && cur.next!=null){
pre = pre.next;
cur = cur.next.next;
}
if(cur!=null) pre = pre.next;//找到中间节点
// 2.反转后半部分
ListNode right = reverseList(pre);
// 3.双指针对比是否相同
ListNode left = head;
while(right!=null){
if(left.val!=right.val) return false;
left = left.next;
right = right.next;
}
return true;
}
}
3 环形链表
* 【环形链表】
* 160、相交链表，给你两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null
* 141、环形链表
* 142、环形链表 II
* @author sommer1111
* @date 2021/5/31 10:04
public class all {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
// 双指针遍历对比
ListNode node1 = headA;
ListNode node2 = headB;
// 退出循环有两种情况
// 1.node1 = node2 找到链表的交点
// 2.node1 = ndoe2 = null,经过两次遍历之后，都指向了尾节点还没有交点，退出循环
while (node1 != node2) {
// 简称：我吹过你吹过的晚风
// 再走一遍你来时的路，这样两个人走的距离是相等的，如果有相交一定会重合
node1 = node1 == null ? headB : node1.next;
node2 = node2 == null ? headA : node2.next;
}
return node1;
}
public boolean hasCycle(ListNode head) {
// 快慢双指针
if(head==null || head.next==null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(slow!=fast){
if(fast==null || fast.next==null) return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {//拿个节点从头开始遍历，相等时就是入口
ListNode cur = head;
while (cur != slow) {
cur = cur.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
4 合并链表
package _03_ListNode;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
* 合并链表
* 21、合并两个有序链表
* 23、合并 k 个有序链表,将 k 个有序的链表合并
*
* @author sommer1111
* @date 2021/5/31 10:04
*/
public class all {
// 有二法：双指针比较，递归
// 双指针就是归并排序的链表实现。
// 想到了之前看到的一句话，归并排序非常适合用来作为链表归并排序的方式
// 所以在java的默认排序方式中，对于基本数据类型使用的是优化的快排
// 而对于引用数据类型，使用的是优化的归并排序
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null || l2==null) return l1==null?l2:l1;
ListNode newHead = new ListNode(0);
ListNode cur = newHead;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next=l1==null?l2:l1;
return newHead.next;
}
// 法二：递归
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next = mergeTwoLists2(l1.next,l2);
return l1;
}else{
l2.next = mergeTwoLists2(l1,l2.next);
return l2;
}
}
// 一眼想就是当做特殊的两个合并,每次选两个
// 方法二：递归分治，完全就是归并排序的思想
public ListNode mergeKLists(ListNode[] lists) {
return mergeFrom(lists,0,lists.length-1);
}
// 1.先分
public ListNode mergeFrom(ListNode[] lists,int left,int right) {
// left=right时表示已经全部合并完了
if(left==right) return lists[left];
if(left<right){
int mid = left + (right-left)/2;
return mergeTwoLists2(
mergeFrom(lists,left,mid),
mergeFrom(lists,mid+1,right));
}
return null;
}
}
5 排序链表
还有两题，写不下去了，先放着。。。。
* 排序链表 * 147、对链表进行插入排序 * 148、排序链表
这篇关于2021-8-6 复习链表的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-06-26结对编程到底难不难？答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图，怎么办？
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗？
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡？
- 2024-05-31全网首发第二弹！软考2024年5月《软件设计师》真题+解析+答案！（11-20题）
- 2024-05-31全网首发！软考2024年5月《软件设计师》真题+解析+答案！（21-30题）
