• 【小嘟陪你刷题06】合并两个有序链表、链表分割、删除链表重复节点、链表的回文结构


    前言

    此篇接着学习链表的一些操作,解法比较通俗易懂,比较简单,如果有更好的方法,欢迎在评论区进行讨论!

    一、合并两个有序链表

    在这里插入图片描述

    1.1 迭代

    在这里插入图片描述

    /**
     1. Definition for singly-linked list.
     2. public class ListNode {
     3.     int val;
     4.     ListNode next;
     5.     ListNode() {}
     6.     ListNode(int val) { this.val = val; }
     7.     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     8. }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            ListNode newHead = new ListNode(-1);
            ListNode tmp = newHead;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) {
                    tmp.next = list1;
                    list1 = list1.next;
                    tmp = tmp.next;
                } else {
                    tmp.next = list2;
                    list2 = list2.next;
                    tmp = tmp.next;
                }
            }
            if (list1 != null) {
                tmp.next = list1;
            }
            if (list2 != null) {
                tmp.next = list2;
            }
            return newHead.next;
        
        }
    }
    

    复杂度分析

    1. 时间复杂度:O(n + m),其中 n 和 m 分别为两个链表的长度。
    2. 空间复杂度:O(1)。我们只需要常数的空间存放若干变量。

    二、链表分割

    在这里插入图片描述

    2.1 分割成两个部分

    (1)先令cur=head,把链表分成两段,第一段为小于目标值得,第二段为大于等于目标值的
    (2)让cur遍历链表并判断节点放入哪一段里,直到cur==null;
    (3)若cur.val=x,一样的方法
    (4)循环结束后把第二段尾插到第一段最后就行了,返回bs
    (5)最后要判断所有节点都在某一段的情况,若都在第二段,头结点就应是as
    (6)在判断若第二段有节点,则要把第二段ae.next设为null,防止链表成环

    在这里插入图片描述

    import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            ListNode bs = null;
            ListNode be = null;
            ListNode as = null;
            ListNode ae = null;
            ListNode cur = pHead;
            
            while (cur != null) {
                if (cur.val < x) {
                    // 1.第一次
                    if (bs == null) {
                        bs = cur;
                        be = cur;
                    }
                     else {
                        // 2.不是第一次  尾插法
                        be.next = cur;
                        be = be.next;
                    }
                } else {
                    // 1.第一次
                    if (as == null) {
                        as = cur;
                        ae = cur;
                    } else {
                        // 2.不是第一次
                        ae.next = cur;
                        ae = ae.next;
                    }
                }
                cur = cur.next;
            }
    
            if (bs == null) {
                return as;
            }
            
            be.next = as;
            if (as != null) {
                ae.next = null;
            }
            return bs;
        }
    }
    

    三、删除链表重复节点

    在这里插入图片描述

    3.1 直接比较删除

    这是一个升序链表,重复的节点都连在一起,我们就可以很轻易地比较到重复的节点,然后将所有的连续相同的节点都跳过,连接不相同的第一个节点。

    1. 给链表前加上表头,方便可能的话删除第一个节点。
    2. 遍历链表,每次比较相邻两个节点,如果遇到了两个相邻节点相同,则新开内循环将这一段所有的相同都遍历过去
    3. 在第二步中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
    4. 返回时去掉添加的表头。
      请添加图片描述
    /*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public ListNode deleteDuplication(ListNode head) {
            ListNode cur = head;
            ListNode newHead = new ListNode(-1);
            ListNode tmp = newHead;
            while (cur != null) {
                if (cur.next != null && cur.val == cur.next.val) {
                    while (cur.next != null && cur.val == cur.next.val) {
                        cur = cur.next;
                    }
                    cur = cur.next;
                } else {
                    tmp.next = cur;
                    tmp = tmp.next;
                    cur = cur.next;
                }
            }
            tmp.next = null;
            return newHead.next;
        }
    }
    

    四、链表的回文结构

    在这里插入图片描述

    4.1 快慢指针

    1. 使用快慢指针找中间节点
    2. 逆置
    3. 判断回文
    import java.util.*;
    
    /*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class PalindromeList {
        public boolean chkPalindrome(ListNode head) {
            // write code here
             // 1 使用快慢指针找到链表的中间节点
            if (head == null) return true;
            ListNode fast = head;
            ListNode slow = head;
    
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
    		//2 对后半段链表进行逆置操作
            ListNode cur = slow.next;
            while (cur != null) {
                ListNode curNext = cur.next;
                cur.next = slow;
                slow = cur;
                cur = curNext;
            }
            //3 比较判断回文
            while (head != slow) {
                if (head.val != slow.val) {
                    return false;
                }
                if (head.next == slow) {
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
    
        }
    }
    
  • 相关阅读:
    PE文件之导入表
    前端用户体验设计:创造卓越的用户界面和交互
    Clickhouse系列二:Join调优策略
    C语言实现的多项式合并运算系统
    云安全-云服务器(RAM)后渗透
    基于ssm技术的校自助阅览室的设计与实现毕业设计源码242326
    ElementUI组件库,分页组件靠右显示
    EN 1154建筑五金件受控关门装置—CE认证
    前端性能优化——渲染优化
    Win9x在Ryzen等新处理器虚拟机抽风的原因及补丁
  • 原文地址:https://blog.csdn.net/weixin_61341342/article/details/127112506